Citation
Krishnendu Chatterjee, Tom Henzinger, Nir Piterman. "Algorithms for Buchi Games". GDV 06, August, 2006.

Abstract
The classical algorithm for solving Buchi games requires time O(n * m) for game graphs with n states and m edges. For game graphs with constant outdegree, the best known algorithm has running time O(n*n /log n). We present two new algorithms for Buchi games. First, we give an algorithm that performs at most O(m) more work than the classical algorithm, but runs in time O(n) on infinitely many graphs of constant outdegree on which the classical algorithm requires time O(n*n). Second, we give an algorithm with running time O(n * m *log delta(n)/log n), where 1<= delta(n) <= n, is the outdegree of the game graph. Note that this algorithm performs asymptotically better than the classical algorithm if delta(n)=O(log n).

Electronic downloads

• main.ps · application/postscript · 401 kbytes

• HTML

  Krishnendu Chatterjee, Tom Henzinger, Nir Piterman. <a
  href="http://chess.eecs.berkeley.edu/pubs/238.html"
  >Algorithms for Buchi Games</a>, GDV 06, August,
  2006.

• Plain text

  Krishnendu Chatterjee, Tom Henzinger, Nir Piterman.
  "Algorithms for Buchi Games". GDV 06, August, 2006.

• BibTeX

  @inproceedings{ChatterjeeHenzingerPiterman06_AlgorithmsForBuchiGames,
      author = {Krishnendu Chatterjee and Tom Henzinger and Nir
                Piterman},
      title = {Algorithms for Buchi Games},
      booktitle = {GDV 06},
      month = {August},
      year = {2006},
      abstract = {The classical algorithm for solving Buchi games
                requires time O(n * m) for game graphs with n
                states and m edges. For game graphs with constant
                outdegree, the best known algorithm has running
                time O(n*n /log n). We present two new algorithms
                for Buchi games. First, we give an algorithm that
                performs at most O(m) more work than the classical
                algorithm, but runs in time O(n) on infinitely
                many graphs of constant outdegree on which the
                classical algorithm requires time O(n*n). Second,
                we give an algorithm with running time O(n * m
                *log delta(n)/log n), where 1<= delta(n) <= n, is
                the outdegree of the game graph. Note that this
                algorithm performs asymptotically better than the
                classical algorithm if delta(n)=O(log n). },
      URL = {http://chess.eecs.berkeley.edu/pubs/238.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.