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.
