conference paper
Algorithms for Büchi Games
published
Krishnendu
Chatterjee
author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X
Thomas A
Henzinger
author 40876CD8-F248-11E8-B48F-1D18A9856A870000−0002−2985−7724
Nir
Piterman
author
GDV: Games in Design and Verification
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).
ACM2006
yes
Chatterjee, Krishnendu, et al. <i>Algorithms for Büchi Games</i>. ACM, 2006.
Chatterjee, Krishnendu, Thomas A Henzinger, and Nir Piterman. “Algorithms for Büchi Games.” ACM, 2006.
K. Chatterjee, T. A. Henzinger, and N. Piterman, “Algorithms for Büchi Games,” presented at the GDV: Games in Design and Verification, 2006.
K. Chatterjee, T.A. Henzinger, N. Piterman, in:, ACM, 2006.
Chatterjee K, Henzinger TA, Piterman N. 2006. Algorithms for Büchi Games. GDV: Games in Design and Verification.
Chatterjee, K., Henzinger, T. A., & Piterman, N. (2006). Algorithms for Büchi Games. Presented at the GDV: Games in Design and Verification, ACM.
Chatterjee K, Henzinger TA, Piterman N. Algorithms for Büchi Games. In: ACM; 2006.
35002018-12-11T12:03:39Z2021-01-12T07:43:53Z