Please use this identifier to cite or link to this item:
Title: Algorithms for Büchi Games
Authors: Chatterjee, K.
Henzinger, Thomas A.
Piterman, Nir
First Published: 16-May-2008
Citation: arXiv:0805.2620v1 Computer Science and Game Theory 2008
Abstract: The classical algorithm for solving B\"uchi 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\"uchi 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\delta(n)/\log n)$, where $1\le\delta(n)\le 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)$.
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2008, the author.
Description: 11 Pages, Published in GDV 06 (Games in Design and Verification)
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
0805.2620v1.pdfPost-review (final submitted)183.67 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.