Algorithms for Büchi Games

Details Algorithms for Büchi Games Algorithms for Büchi Games

2008-05-16

arxiv.org/abs/0805.2620v1

Computer Science

Computer Science and Game Theory

11 Pages, Published in GDV 06 (Games in Design and Verification)

Scientific paper

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)$.

Affiliated with

Also associated with

No associations

Rating

Algorithms for Büchi Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithms for Büchi Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Büchi Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-613802