On Winning Conditions of High Borel Complexity in Pushdown Games

Simple item page
dc.creatorFinkel, Olivier
dc.date2008-03-12
dc.date.accessioned2026-07-07T12:17:36Z
dc.date.available2026-07-07T12:17:36Z
dc.descriptionSome decidable winning conditions of arbitrarily high finite Borel complexity for games on finite graphs or on pushdown graphs have been recently presented by O. Serre in [ Games with Winning Conditions of High Borel Complexity, in the Proceedings of the International Conference ICALP 2004, LNCS, Volume 3142, p. 1150-1162 ]. We answer in this paper several questions which were raised by Serre in the above cited paper. We first show that, for every positive integer n, the class C_n(A), which arises in the definition of decidable winning conditions, is included in the class of non-ambiguous context free omega languages, and that it is neither closed under union nor under intersection. We prove also that there exists pushdown games, equipped with such decidable winning conditions, 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.
dc.identifierhttps://arxiv.org/abs/0803.1830
dc.identifierhttp://arxiv.org/abs/0803.1830
dc.identifierFundamenta Informaticae 66 (3) (2005) 277-298
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/212130
dc.subjectLogic in Computer Science
dc.subjectComputer Science and Game Theory
dc.subjectLogic
dc.titleOn Winning Conditions of High Borel Complexity in Pushdown Games
dc.typetext

Files

Collections

arXiv