×

Polishness of some topologies related to word or tree automata. (English) Zbl 1454.03061

Summary: We prove that the Büchi topology and the automatic topology are Polish. We also show that this cannot be fully extended to the case of a space of infinite labelled binary trees; in particular the Büchi and the Muller topologies are not Polish in this case.

MSC:

03E15 Descriptive set theory
03D05 Automata and formal grammars in connection with logical questions
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: arXiv

References:

[1] A. Arnold, J. Duparc, F. Murlak, and D. Niwi´nski. On the topological complexity of tree languages. In J. Flum, E. Gr¨adel, and T. Wilke, editors, Logic and Automata: History and Perspectives, pages 9-28. Amsterdam University Press, 2007. · Zbl 1244.03116
[2] J. R. B¨uchi. On a decision method in restricted second order arithmetic. In Stanford University Press, editor, Proceedings of the 1960 International Congress on Logic Methodology and Philosophy of Science, pages 1-11. Stanford University Press, 1962. · Zbl 0147.25103
[3] O. Carton, O. Finkel, and D. Lecomte. Polishness of Some Topologies Related to Automata. In V. Goranko and M. Dam, editors, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), volume 82 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1-22:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. · Zbl 1454.03061
[4] F. Cavallari, H. Michalewski, and M. Skrzypczak. A characterisation of Π02regular tree languages. In K. G. Larsen, H. L. Bodlaender, and J.-F. Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, volume 83 of LIPIcs, pages 56:1-56:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. · Zbl 1441.68118
[5] C. Choffrut and S. Grigorieff. Uniformization of rational relations. In Juhani Karhum¨aki, Hermann A. · Zbl 0944.68107
[6] R. S. Cohen and A. Y. Gold. ω-computations on Turing machines. Theoretical Computer Science, 6:1-23, 1978. · Zbl 0368.68057
[7] J. Duparc, O. Finkel, and J.-P. Ressayre. The Wadge hierarchy of Petri nets ω-languages. In V. Brattka, H. Diener, and D. Spreen, editors, Logic, Computation, Hierarchies, volume 4 of Ontos Mathematical Logic, collection of papers published in Honor of Victor Selivanov at the occasion of his sixtieth birthday, pages 109-138. Ontos-Verlag, 2014. · Zbl 1310.68130
[8] O. Finkel. Borel ranks and Wadge degrees of omega context free languages. Mathematical Structures in Computer Science, 16(5):813-840, 2006. · Zbl 1121.03047
[9] O. Finkel. The complexity of infinite computations in models of set theory. Logical Methods in Computer Science, 5(4:4):1-19, 2009. · Zbl 1191.03034
[10] O. Finkel. Ambiguity of ω-languages of Turing machines. Logical Methods in Computer Science, 10(3:12):1- 18, 2014. · Zbl 1337.03056
[11] O. Finkel and D. Lecomte. Classical and effective descriptive complexities of ω-powers. Annals of Pure and Applied Logic, 160(2):163-191, 2009. · Zbl 1170.03025
[12] O. Finkel and D. Lecomte. Decision problems for Turing machines. Information Processing Letters, 109:1223-1226, 2009. · Zbl 1206.68115
[13] O. Finkel and P. Simonnet. Topology and ambiguity in omega context free languages. Bulletin of the Belgian Mathematical Society, 10(5):707-722, 2003. · Zbl 1080.68054
[14] S. Gao. Invariant descriptive set theory, volume 293 of Pure and Applied Mathematics (Boca Raton). CRC Press, Boca Raton, FL, 2009. · Zbl 1154.03025
[15] E. Gr¨adel, W. Thomas, and W. Wilke, editors. Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science. Springer, 2002.
[16] L. A. Harrington, A. S. Kechris, and A. Louveau. A Glimm-Effros dichotomy for Borel equivalence relations. Journal of the American Mathematical Society, 3:903-928, 1990. · Zbl 0778.28011
[17] S. Hoffmann, S. Schwarz, and L. Staiger. Shift-invariant topologies for the Cantor space Xω. Theoretical Computer Science, 679:145161, 2017. · Zbl 1386.68090
[18] S. Hoffmann and L. Staiger. Subword metrics for infinite words. In F. Drewes, editor, Implementation and Application of Automata - 20th International Conference, CIAA 2015, Ume˚a, Sweden, August 18-21, 2015, Proceedings, volume 9223 of Lecture Notes in Computer Science, pages 165-175. Springer, 2015. · Zbl 1465.68150
[19] A. S. Kechris. Classical descriptive set theory. Springer-Verlag, New York, 1995. · Zbl 0819.04002
[20] A. S. Kechris, S. Solecki, and S. Todorˇcevi´c. Borel chromatic numbers. Advances in Mathematics, 141(1):1-44, 1999. · Zbl 0918.05052
[21] L. H. Landweber. Decision problems for ω-automata. Mathematical Systems Theory, 3(4):376-384, 1969. · Zbl 0182.02402
[22] D. Lecomte. A dichotomy characterizing analytic digraphs of uncountable Borel chromatic number in any dimension. Transactions of the American Mathematical Society, 361(8):4181-4193, 2009. · Zbl 1169.03037
[23] D. Lecomte. Potential Wadge classes. Memoirs of the American Mathematical Society, 221(1038):vi+83, 2013.
[24] H. Lescow and W. Thomas. Logical specifications of infinite computations. In J. W. de Bakker, W. P. de Roever, and G. Rozenberg, editors, A Decade of Concurrency, volume 803 of Lecture Notes in Computer Science, pages 583-621. Springer, 1994.
[25] M. Lothaire. Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2002. · Zbl 1001.68093
[26] A. Louveau. Ensembles analytiques et bor´eliens dans les espaces produit, volume 78. Ast´erisque (SMF), 1980. · Zbl 0526.03030
[27] B. D. Miller. The graph-theoretic approach to descriptive set theory. Bulletin of Symbolic Logic, 18(4):554- 575, 2012. · Zbl 1361.03047
[28] H. Michalewski, M. Mio, and M. Skrzypczak. Monadic second order logic with measure and category quantifiers. Logical Methods in Computer Science, 14(2):Paper No. 2, 29, 2018. · Zbl 1459.03054
[29] Y. N. Moschovakis. Descriptive set theory. North-Holland Publishing Co., Amsterdam, 1980. · Zbl 0433.03025
[30] Y. N. Moschovakis. Descriptive set theory, volume 155 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, second edition, 2009. · Zbl 1172.03026
[31] F. Murlak. The Wadge hierarchy of deterministic tree languages. Logical Methods in Computer Science, · Zbl 1134.68030
[32] D. Niwi´nski. An example of non Borel set of infinite trees recognizable by a Rabin automaton. 1985. in Polish, manuscript.
[33] D. Niwi´nski and I. Walukiewicz. A gap property of deterministic tree languages. Theoretical Computer Science, 303(1):215-231, 2003. Logic and complexity in computer science (Cr´eteil, 2001). · Zbl 1044.68120
[34] D. Perrin and J.- ´E. Pin. Infinite words, automata, semigroups, logic and games, volume 141 of Pure and Applied Mathematics. Elsevier, 2004. · Zbl 1094.68052
[35] S. Schwarz and L. Staiger. Topologies refining the Cantor topology on Xω. In C. S. Calude and V. Sassone, editors, Theoretical Computer Science - 6th IFIP TC 1/WG 2.2 International Conference, TCS 2010, Held as Part of WCC 2010, Brisbane, Australia, September 20-23, 2010. Proceedings, volume 323 of IFIP Advances in Information and Communication Technology, pages 271-285. Springer, 2010. · Zbl 1198.68162
[36] V. L. Selivanov. Wadge degrees of ω-languages of deterministic Turing machines. RAIRO-Theoretical Informatics and Applications, 37(1):67-83, 2003. · Zbl 1048.03031
[37] V. L. Selivanov. Wadge degrees of ω-languages of deterministic Turing machines. In Proceedings of the International Conference STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, volume 2607 of Lecture Notes in Computer Science, pages 97-108. Springer, 2003. · Zbl 1036.03033
[38] V. L. Selivanov. Wadge reducibility and infinite computations. Mathematics in Computer Science, 2(1):5-36, 2008. · Zbl 1157.03018
[39] O. Serre. Games with winning conditions of high Borel complexity. Theoretical Computer Science, 350(2-3):345-372, 2006. · Zbl 1125.91024
[40] P. Simonnet. Automates et th´eorie descriptive. PhD thesis, Universit´e Paris VII, 1992.
[41] M. Skrzypczak. Descriptive Set Theoretic Methods in Automata Theory - Decidability and Topological Complexity, volume 9802 of Lecture Notes in Computer Science. Springer, 2016. · Zbl 1375.03003
[42] L. Staiger. ω-languages. In Handbook of formal languages, Vol. 3, pages 339-387. Springer, Berlin, 1997. · Zbl 0866.68057
[43] L. Staiger. On the power of reading the whole infinite input tape. Grammars, 2 (3):247-257, 1999. · Zbl 0967.68099
[44] W. Thomas. Automata on infinite objects. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, Formal models and semantics, pages 135-191. Elsevier, 1990. · Zbl 0714.68001
[45] K. Wagner. On ω-regular sets. Information and Control, 43(2):123-177, 1979. · Zbl 0434.68061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.