Citation
Krishnendu Chatterjee, Tom Henzinger. "Value Iteration". Unpublished article, 2007; A Survey Paper submitted for publication in "25 Years in Model Checking".

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.

Electronic downloads

• main.ps · application/postscript · 545 kbytes

• HTML

  Krishnendu Chatterjee, Tom Henzinger. <a
  href="http://chess.eecs.berkeley.edu/pubs/239.html"
  ><i>Value Iteration</i></a>,
  Unpublished article,  2007; A Survey Paper submitted for
  publication in "25 Years in Model Checking".

• Plain text

  Krishnendu Chatterjee, Tom Henzinger. "Value
  Iteration". Unpublished article,  2007; A Survey Paper
  submitted for publication in "25 Years in Model
  Checking".

• BibTeX

  @unpublished{ChatterjeeHenzinger07_ValueIteration,
      author = {Krishnendu Chatterjee and Tom Henzinger},
      title = {Value Iteration},
      year = {2007},
      note = {A Survey Paper submitted for publication in "25
                Years in Model Checking"},
      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.},
      URL = {http://chess.eecs.berkeley.edu/pubs/239.html}
  }
  

Posted by Krishnendu Chatterjee, PhD on 13 May 2007.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.