The cost of exactness in quantitative reachability Book Section


Author(s): Chatterjee, Krishnendu; Doyen, Laurent; Henzinger, Thomas A
Article/Chapter Title: The cost of exactness in quantitative reachability
Title Series: LNCS
Affiliation IST Austria
Abstract: In the analysis of reactive systems a quantitative objective assigns a real value to every trace of the system. The value decision problem for a quantitative objective requires a trace whose value is at least a given threshold, and the exact value decision problem requires a trace whose value is exactly the threshold. We compare the computational complexity of the value and exact value decision problems for classical quantitative objectives, such as sum, discounted sum, energy, and mean-payoff for two standard models of reactive systems, namely, graphs and graph games.
Book Title: Models, Algorithms, Logics and Tools
Volume: 10460
ISBN: 978-3-319-63121-9
Publisher: Springer  
Date Published: 2017-01-01
Start Page: 367
End Page: 381
DOI: 10.1007/978-3-319-63121-9_18
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work