*banner
 

Value Iteration
Krishnendu Chatterjee, Tom Henzinger

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
Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess