On Winning Conditions of High Borel Complexity in Pushdown Games

• Autorzy: Finkel O.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

pushdown automata; infinite two-player games; pushdown games; winning conditions; Borel complexity; context-free language; closure under boolean operations; set of winning positions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 66, nr 3
• Strony: 277--298
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Finkel O.

• Equipe de Logique Mathématique, U.F.R. de Mathematiques, Université Paris 7, 2 Place Jussieu, 75251 Paris, cedex 05, France,

Bibliografia

• [1] Autebert, J.-M., Berstel, J., Boasson, L.: Context free languages and pushdown automata, in: Handbook of formal languages, Vol. 1, Springer-Verlag, 1996.
• [2] Berstel, J.: Transductions and context free languages, Teubner Studienbücher Informatik, 1979.
• [3] Bouquet, A., Serre, O., Walukiewicz, I.: Pushdown games with the unboundedness and regular conditions, in: Proceedings of the International Conference FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 23rd Conference, vol. 2914 of Lecture Notes in Computer Science, Springer, 2003, 88–99.
• [4] Cachat, T.: Symbolic strategy synthesis for games on pushdown graphs, in: Proceedings of the International Conference ICALP 2002, vol. 2380 of Lecture Notes in Computer Science, Springer, 2002, 704–715.
• [5] Cachat, T.: Two-way tree automata solving pushdown games, in: Automata, Logics, and Infinite Games (E. Grädel, W. Thomas, T. Wilke, Eds.), vol. 2500 of Lecture Notes in Computer Science, Springer, 2002, 303–317.
• [6] Cachat, T., Duparc, J., Thomas, W.: Solving pushdown games with a Σ_3-winning condition, in: Proceedings of the 11th Annual Conference of the European Association for Computer Science Logic, CSL 2002, vol. 2471 of Lecture Notes in Computer Science, Springer, 2003, 322–336.
• [7] Cohen, R., Gold, A.: Theory of -languages, parts one and two, Journal of Computer and System Science, 15, 1977, 169–208.
• [8] Cohen, R., Gold, A.: -computations on deterministic pushdown machines, Journal of Computer and System Science, 16, 1978, 275–300.
• [9] Duparc, J.: Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank, Journal of Symbolic Logic, 66(1), 2001, 56–86.
• [10] Finkel, O.: Ambiguity in omega context free languages, Theoretical Computer Science, 301(1-3), 2003, 217–270.
• [11] Gimbert, H.: Parity and exploration games on infinite graphs, in: Proceedings of the 13th Annual Conference of the European Association for Computer Science Logic, CSL 2004, vol. 3210 of Lecture Notes in Computer Science, Springer, 2004, 56–70.
• [12] Hopcroft, J. E., Motwani, R., Ullman, J. D.: Introduction to automata theory, languages, and computation, Addison-Wesley Publishing Co., Reading, Mass., 2001, Addison-Wesley Series in Computer Science.
• [13] Hopcroft, J. E., Ullman, J. D.: Introduction to automata theory, languages, and computation, Addison-Wesley Publishing Co., Reading, Mass., 1979, Addison-Wesley Series in Computer Science.
• [14] Kechris, A. S.: Classical descriptive set theory, Springer-Verlag, New York, 1995.
• [15] Kuratowski, K.: Topology, Academic Press, New York, 1966.
• [16] Lescow, H., Thomas,W.: Logical specifications of infinite computations, in: A Decade of Concurrency (J.W. de Bakker, W. P. de Roever, G. Rozenberg, Eds.), vol. 803 of Lecture Notes in Computer Science, Springer, 1994, 583–621.
• [17] Serre, O.: Note on winning positions on pushdown games with -regular conditions, Information Processing Letters, 85, 2003, 285–291.
• [18] Serre, O.: Contribution `a l’´etude des jeux sur des graphes de processus `a pile, Ph.D. Thesis, Université Paris VII, 2004.
• [19] Serre, O.: Games with winning conditions of high borel complexity, in: Proceedings of the International Conference ICALP 2004, vol. 3142 of Lecture Notes in Computer Science, Springer, 2004, 1150–1162.
• [20] Serre, O.: Games with winning conditions of high borel complexity, 2004, To appear in Theoretical Computer Science, available from : http://www.liafa.jussieu.fr/ serre.
• [21] Staiger, L.: -languages, in: Handbook of formal languages, Vol. 3, Springer, Berlin, 1997, 339–387.
• [22] Thomas,W.: Automata on infinite objects, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Formal models and semantics, Elsevier, 1990, 135–191.
• [23] Thomas, W.: On the synthesis of strategies in infinite games, in: Proceedings of the International Conference STACS 1995, vol. 900 of Lecture Notes in Computer Science, Springer, 1995, 1–13.
• [24] Thomas, W.: Infinite games and verification (extended abstract of a tutorial), in: Proceedings of the International Conference on Computer Aided Verification CAV 2002, vol. 2404 of Lecture Notes in Computer Science, Springer, 2002, 58–64.
• [25] Walukiewicz, I.: Pushdown processes: games and model checking, Information and Computation, 157, 2000, 234–263.