---
_id: '625'
abstract:
- lang: eng
  text: 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.
acknowledgement: 'This research was supported in part by the Austrian Science Fund
  (FWF) under grants S11402-N23 and S11407-N23 (RiSE/SHiNE), and Z211-N23 (Wittgenstein
  Award), ERC Start grant (279307: Graph Games), Vienna Science and Technology Fund
  (WWTF) through project ICT15-003.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  ama: 'Chatterjee K, Doyen L, Henzinger TA. The cost of exactness in quantitative
    reachability. In: Aceto L, Bacci G, Ingólfsdóttir A, Legay A, Mardare R, eds.
    <i>Models, Algorithms, Logics and Tools</i>. Vol 10460. Theoretical Computer Science
    and General Issues. Springer; 2017:367-381. doi:<a href="https://doi.org/10.1007/978-3-319-63121-9_18">10.1007/978-3-319-63121-9_18</a>'
  apa: Chatterjee, K., Doyen, L., &#38; Henzinger, T. A. (2017). The cost of exactness
    in quantitative reachability. In L. Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay,
    &#38; R. Mardare (Eds.), <i>Models, Algorithms, Logics and Tools</i> (Vol. 10460,
    pp. 367–381). Springer. <a href="https://doi.org/10.1007/978-3-319-63121-9_18">https://doi.org/10.1007/978-3-319-63121-9_18</a>
  chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “The Cost
    of Exactness in Quantitative Reachability.” In <i>Models, Algorithms, Logics and
    Tools</i>, edited by Luca Aceto, Giorgio Bacci, Anna Ingólfsdóttir, Axel Legay,
    and Radu Mardare, 10460:367–81. Theoretical Computer Science and General Issues.
    Springer, 2017. <a href="https://doi.org/10.1007/978-3-319-63121-9_18">https://doi.org/10.1007/978-3-319-63121-9_18</a>.
  ieee: K. Chatterjee, L. Doyen, and T. A. Henzinger, “The cost of exactness in quantitative
    reachability,” in <i>Models, Algorithms, Logics and Tools</i>, vol. 10460, L.
    Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay, and R. Mardare, Eds. Springer, 2017,
    pp. 367–381.
  ista: 'Chatterjee K, Doyen L, Henzinger TA. 2017.The cost of exactness in quantitative
    reachability. In: Models, Algorithms, Logics and Tools. LNCS, vol. 10460, 367–381.'
  mla: Chatterjee, Krishnendu, et al. “The Cost of Exactness in Quantitative Reachability.”
    <i>Models, Algorithms, Logics and Tools</i>, edited by Luca Aceto et al., vol.
    10460, Springer, 2017, pp. 367–81, doi:<a href="https://doi.org/10.1007/978-3-319-63121-9_18">10.1007/978-3-319-63121-9_18</a>.
  short: K. Chatterjee, L. Doyen, T.A. Henzinger, in:, L. Aceto, G. Bacci, A. Ingólfsdóttir,
    A. Legay, R. Mardare (Eds.), Models, Algorithms, Logics and Tools, Springer, 2017,
    pp. 367–381.
date_created: 2018-12-11T11:47:34Z
date_published: 2017-07-25T00:00:00Z
date_updated: 2025-06-02T08:53:45Z
day: '25'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-319-63121-9_18
ec_funded: 1
editor:
- first_name: Luca
  full_name: Aceto, Luca
  last_name: Aceto
- first_name: Giorgio
  full_name: Bacci, Giorgio
  last_name: Bacci
- first_name: Anna
  full_name: Ingólfsdóttir, Anna
  last_name: Ingólfsdóttir
- first_name: Axel
  full_name: Legay, Axel
  last_name: Legay
- first_name: Radu
  full_name: Mardare, Radu
  last_name: Mardare
file:
- access_level: open_access
  checksum: b2402766ec02c79801aac634bd8f9f6c
  content_type: application/pdf
  creator: dernst
  date_created: 2019-11-19T08:06:50Z
  date_updated: 2020-07-14T12:47:25Z
  file_id: '7048'
  file_name: 2017_ModelsAlgorithms_Chatterjee.pdf
  file_size: 192826
  relation: main_file
file_date_updated: 2020-07-14T12:47:25Z
has_accepted_license: '1'
intvolume: '     10460'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 367 - 381
project:
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11402-N23
  name: Moderne Concurrency Paradigms
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: The Wittgenstein Prize
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
publication: Models, Algorithms, Logics and Tools
publication_identifier:
  isbn:
  - 978-3-319-63120-2
  issn:
  - 0302-9743
publication_status: published
publisher: Springer
publist_id: '7170'
quality_controlled: '1'
scopus_import: '1'
series_title: Theoretical Computer Science and General Issues
status: public
title: The cost of exactness in quantitative reachability
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10460
year: '2017'
...