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

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	285-291
Nombre de pages	7
journal	Information Processing Letters
Volume	85
Numéro de publication	6
Les DOIs	https://doi.org/10.1016/S0020-0190(02)00445-3
état	Publié - 31 mars 2003
Modification externe	Oui

Accès au document

10.1016/S0020-0190(02)00445-3

Contient cette citation

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

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

Résumé

Accès au document

Empreinte digitale

Contient cette citation