Note on winning positions on pushdown games with ω-regular conditions |
| |
Authors: | Olivier Serre |
| |
Affiliation: | LIAFA, Université Paris VII, 2 Place Jussieu, Paris 75005, France |
| |
Abstract: | 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. |
| |
Keywords: | Automata Games Infinite graphs Pushdown processes |
本文献已被 ScienceDirect 等数据库收录! |
|