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

Olivier Serre

doi:10.1016/S0020-0190(02)00445-3

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

Olivier Serre

Université Paris 7

Research output: Contribution to journal › Article › peer-review

35 Citations (Scopus)

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.

Original language	English
Pages (from-to)	285-291
Number of pages	7
Journal	Information Processing Letters
Volume	85
Issue number	6
DOIs	https://doi.org/10.1016/S0020-0190(02)00445-3
Publication status	Published - 31 Mar 2003
Externally published	Yes

Keywords

Automata
Games
Infinite graphs
Pushdown processes

Access to Document

10.1016/S0020-0190(02)00445-3

Cite this

@article{b9a8ac85b6f245778eae15fedf6d4074,

title = "Note on winning positions on pushdown games with ω-regular conditions",

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",

author = "Olivier Serre",

year = "2003",

month = mar,

day = "31",

doi = "10.1016/S0020-0190(02)00445-3",

language = "English",

volume = "85",

pages = "285--291",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

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

AU - Serre, Olivier

PY - 2003/3/31

Y1 - 2003/3/31

N2 - 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.

AB - 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.

KW - Automata

KW - Games

KW - Infinite graphs

KW - Pushdown processes

U2 - 10.1016/S0020-0190(02)00445-3

DO - 10.1016/S0020-0190(02)00445-3

M3 - Article

AN - SCOPUS:0037475068

SN - 0020-0190

VL - 85

SP - 285

EP - 291

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this