---
OA_type: closed access
_id: '3872'
abstract:
- lang: eng
  text: We survey value iteration algorithms on graphs. Such algorithms can be used
    for determining the existence of certain paths (model checking), the existence
    of certain strategies (game solving), and the probabilities of certain events
    (performance analysis). We classify the algorithms according to the value domain
    (boolean, probabilistic, or quantitative); according to the graph structure (nondeterministic,
    probabilistic, or multi-player); according to the desired property of paths (Borel
    level 1, 2, or 3); and according to the alternation depth and convergence rate
    of fixpoint computations.
acknowledgement: This research was supported in part by the Swiss National Science
  Foundation and by the NSF grants CCR-0225610 and CCR-0234690.
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: 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, Henzinger TA. Value iteration. In: <i>25 Years in Model Checking</i>.
    Vol 5000. Springer Nature; 2008:107-138. doi:<a href="https://doi.org/10.1007/978-3-540-69850-0_7">10.1007/978-3-540-69850-0_7</a>'
  apa: Chatterjee, K., &#38; Henzinger, T. A. (2008). Value iteration. In <i>25 Years
    in Model Checking</i> (Vol. 5000, pp. 107–138). Springer Nature. <a href="https://doi.org/10.1007/978-3-540-69850-0_7">https://doi.org/10.1007/978-3-540-69850-0_7</a>
  chicago: Chatterjee, Krishnendu, and Thomas A Henzinger. “Value Iteration.” In <i>25
    Years in Model Checking</i>, 5000:107–38. Springer Nature, 2008. <a href="https://doi.org/10.1007/978-3-540-69850-0_7">https://doi.org/10.1007/978-3-540-69850-0_7</a>.
  ieee: K. Chatterjee and T. A. Henzinger, “Value iteration,” in <i>25 Years in Model
    Checking</i>, vol. 5000, Springer Nature, 2008, pp. 107–138.
  ista: 'Chatterjee K, Henzinger TA. 2008.Value iteration. In: 25 Years in Model Checking.
    LNCS, vol. 5000, 107–138.'
  mla: Chatterjee, Krishnendu, and Thomas A. Henzinger. “Value Iteration.” <i>25 Years
    in Model Checking</i>, vol. 5000, Springer Nature, 2008, pp. 107–38, doi:<a href="https://doi.org/10.1007/978-3-540-69850-0_7">10.1007/978-3-540-69850-0_7</a>.
  short: K. Chatterjee, T.A. Henzinger, in:, 25 Years in Model Checking, Springer
    Nature, 2008, pp. 107–138.
date_created: 2018-12-11T12:05:38Z
date_published: 2008-01-01T00:00:00Z
date_updated: 2026-05-29T10:39:25Z
day: '01'
doi: 10.1007/978-3-540-69850-0_7
extern: '1'
fulldoi: https://doi.org/10.1007/978-3-540-69850-0_7
intvolume: '      5000'
language:
- iso: eng
month: '01'
oa_version: None
page: 107 - 138
publication: 25 Years in Model Checking
publication_identifier:
  eisbn:
  - '9783540698500'
  isbn:
  - '9783540698494'
publication_status: published
publisher: Springer Nature
publist_id: '2299'
status: public
title: Value iteration
type: book_chapter
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 5000
year: '2008'
...