Value iteration Book Section


Author(s): Chatterjee, Krishnendu; Henzinger, Thomas A
Article/Chapter Title: Value iteration
Title Series: LNCS
Affiliation
Abstract: 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.
Book Title: 25 Years in Model Checking
Volume: 5000
ISBN: 978-3-540-69849-4
Publisher: Springer  
Publication Place: Berlin, Heidelberg
Date Published: 2008-01-01
Start Page: 107
End Page: 138
Sponsor: This research was supported in part by the Swiss National Science Foundation and by the NSF grants CCR-0225610 and CCR-0234690.
DOI: 10.1007/978-3-540-69850-0_7
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work