✦ LIBER ✦

Note on winning positions on pushdown games with ω-regular conditions

✍ Scribed by Olivier Serre

Book ID: 104136883
Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 104 KB
Volume: 85
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(02)00445-3

No coin nor oath required. For personal study only.

✦ Synopsis

We consider infinite two-player games on pushdown graphs. For parity winning conditions, we show that the set of winning positions of each player is regular and we give an effective construction of an alternating automaton recognizing it. This provides a DEXPTIME procedure to decide whether a position is winning for a given player. Finally, using the same methods, we show, for any ω-regular winning condition, that the set of winning positions for a given player is regular and effective.