10.1007/978-3-319-63121-9_18
Chatterjee, Krishnendu
Krishnendu
Chatterjee0000-0002-4561-241X
Doyen, Laurent
Laurent
Doyen
Henzinger, Thomas A
Thomas A
Henzinger0000−0002−2985−7724
The cost of exactness in quantitative reachability
LNCS
Springer
2017
2018-12-11T11:47:34Z
2020-01-16T12:37:58Z
book_chapter
/record/625
/record/625.json
03029743
192826 bytes
application/pdf
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.