Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: pushdown games

Sortuj według:

Ogranicz wyniki do:

On Winning Conditions of High Borel Complexity in Pushdown Games

Finkel O.

Fundamenta Informaticae

2005

Vol. 66, nr 3

277--298

In a recent paper [19,20] Serre has presented some decidable winning conditions [...] 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 \mathbbCn(A), defined in [20], and show that these classes are included in the class of non-ambiguous context free w-languages. Moreover from the study of a larger class \mathbbCln(A) we infer that the complements of languages in \mathbbCn(A) are also non-ambiguous context free w-languages. We conclude the study of classes \mathbbCn(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 [...], 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.