Value Iteration

Krishnendu Chatterjee and Thomas A. Henzinger

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.

In 25 Years of Model Checking, Lecture Notes in Computer Science 5000, Springer, 2008, pp. 107-138.

Download inofficial, sometimes updated PostScript / PDF document. © 2008 Springer.