Affiliations: Equipe de Logique Mathématique, U.F.R. de
Mathématiques, Université Paris 7, 2 Place Jussieu 75251 Paris
cedex 05, France. [email protected]
Note: [] Address for correspondence: Equipe de Logique
Mathématique, U.F.R. de Mathématiques, Université Paris 7,
2 Place Jussieu 75251 Paris cedex 05, France
Abstract: In a recent paper [19, 20] Serre has presented some decidable
winning conditions Ω
_{A_1▹…▹A_n▹A_{n+1}} of arbitrarily high
finite Borel complexity for games on finite graphs or on pushdown graphs. We answer in this paper several questions which were raised by Serre
in [19,20]. We study classes C_n(A), defined in [20], and
show that these classes are included in the class of non-ambiguous context free
ω-languages. Moreover from the study of a larger class
C_n^λ(A) we infer that the complements of languages
in C_n(A) are also non-ambiguous context free
ω-languages. We conclude the study of classes C_n(A)
by showing that they are neither closed under union nor under intersection.
We prove also that there exists pushdown games, equipped with
winning conditions in the form
Ω_{A_1▹A_2}, where the winning
sets are not deterministic context free languages, giving examples of winning
sets which are non-deterministic non-ambiguous context free languages,
inherently ambiguous context free languages, or even non context free
languages.
Keywords: Pushdown automata, infinite two-player games, pushdown games, winning conditions, Borel complexity, context free ω-languages, closure under boolean operations, set of winning positions
