Algorithms for Büchi Games
| dc.creator | Chatterjee, Krishnendu | |
| dc.creator | Henzinger, Thomas A. | |
| dc.creator | Piterman, Nir | |
| dc.date | 2008-05-16 | |
| dc.date.accessioned | 2026-07-07T12:19:00Z | |
| dc.date.available | 2026-07-07T12:19:00Z | |
| dc.description | The classical algorithm for solving Büchi games requires time $O(n\cdot 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^2/\log n)$. We present two new algorithms for Bü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(n^2)$. Second, we give an algorithm with running time $O(n\cdot m\cdot\logδ(n)/\log n)$, where $1\leδ(n)\le n$ is the outdegree of the game graph. Note that this algorithm performs asymptotically better than the classical algorithm if $δ(n)=O(\log n)$. | |
| dc.description | 11 Pages, Published in GDV 06 (Games in Design and Verification) | |
| dc.identifier | https://arxiv.org/abs/0805.2620 | |
| dc.identifier | http://arxiv.org/abs/0805.2620 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/212605 | |
| dc.subject | Computer Science and Game Theory | |
| dc.subject | Logic in Computer Science | |
| dc.title | Algorithms for Büchi Games | |
| dc.type | text |