Algorithms for Büchi Games Conference Paper


Author(s): Chatterjee, Krishnendu; Henzinger, Thomas A; Piterman, Nir
Title: Algorithms for Büchi Games
Affiliation
Abstract: The classical algorithm for solving Bu ̈chi 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(n2/logn). We present two new algorithms for Bu ̈chi 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(n2). Second, we give an algorithm with running time O(n · m · log δ(n)/ log n), where 1 ≤ δ(n) ≤ n is the outdegree of the game graph. Note that this algorithm performs asymptotically better than the classical algorithm if δ(n) = O(log n).
Conference Title: GDV: Games in Design and Verification
Conference Dates: August 21, 2006
Conference Location: Seattle, USA
Publisher: ACM  
Date Published: 2006-08-21
Sponsor: This research was supported in part by the AFOSR MURI grant F49620-00-1-0327 and the NSF ITR grant CCR-0225610 and the SNSF under the Indo-Swiss Joint Research Programme.
URL:
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work