Wadge-Wagner hierarchies. (English) Zbl 1528.03197
Pin, Jean-Éric (ed.), Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS). 695-728 (2021).
This contribution delivers an introduction to the connections of descriptive set theory with automata theory and in particular to the well-known Wadge hierarchy. In a second part of the paper, the author treats the so-called Wagner hierarchy of subclasses of \(\omega\)-regular languages, which turned out to be exactly the trace of the Wadge hierarchy over the \(\omega\)-regular languages.
For the entire collection see [Zbl 1470.68001].
For the entire collection see [Zbl 1470.68001].
Reviewer: Klaus D. Kiermeier (Berlin)
MSC:
| 03E15 | Descriptive set theory |
| 03D05 | Automata and formal grammars in connection with logical questions |
References:
| [1] | A. Arnold, J. Duparc, F. Murlak, and D. Niwiński, On the topological complexity of tree languages. In Logic and automata (J. Flum, E. Grädel, and T. Wilke, eds.). History and perspectives. Texts in Logic and Games, 2. Amsterdam University Press, Amsterdam, 2008, 9-28. MR 2508738 Zbl 1244.03116 q.v. 724 · Zbl 1244.03116 |
| [2] | M. Bojańczyk, Weak MSO with the unbounding quantifier. Theory Comput. Syst. 48 (2011), no. 3, 554-576. MR 2770808 Zbl 1227.03051 q.v. 723 · Zbl 1227.03051 |
| [3] | N. Bourbaki, General topology. Chapters 1-4. Translated from the French. Reprint of the 1989 English translation. Elements of Mathematics (Berlin). Springer, Berlin, 1998. MR 1726779 Zbl 0894.54001 q.v. 698 · Zbl 0894.54001 |
| [4] | J. Cabessa and J. Duparc, A game theoretical approach to the algebraic counterpart of the wagner hierarchy. I. Theor. Inform. Appl. 43 (2009), no. 3, 443-461. MR 2541207 Zbl 1175.03021 q.v. 721, 722 · Zbl 1175.03021 |
| [5] | J. Cabessa and J. Duparc, A game theoretical approach to the algebraic counterpart of the wagner hierarchy. II. Theor. Inform. Appl. 43 (2009), no. 3, 463-515. MR 2541208 Zbl 1175.03022 q.v. 721, 722 · Zbl 1175.03021 |
| [6] | J. Cabessa, J. Duparc, A. Facchini, and F. Murlak, The Wadge hierarchy of max-regular languages. In Foundations of software technology and theoretical computer science -FST & TCS 2009 (R. Kannan and K. N. Kumar, eds.). Proceedings of the 29 th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Kanpur, December 15-17, 2009. LIPIcs. Leibniz International Proceedings in Informatics, 4. Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern, 2009, 121-132. MR 2870706 Zbl 1248.68286 q.v. 723 · Zbl 1248.68286 |
| [7] | O. Carton and D. Perrin, Chains and superchains for !-rational sets, automata and semi-groups. Internat. J. Algebra Comput. 7 (1997), no. 6, 673-695. MR 1482963 Zbl 0911.68143 q.v. 721, 722 · Zbl 0911.68143 |
| [8] | O. Carton and D. Perrin, The Wagner hierarchy. Internat. J. Algebra Comput. 9 (1999), no. 5, 597-620. MR 1719703 Zbl 1056.68547 q.v. 721, 722 · Zbl 1056.68547 |
| [9] | J. Dixmier, General topology. Translated from the French by S. K. Berberian. Undergrad-uate Texts in Mathematics. Springer, New York, 1984. MR 0753644 Zbl 0545.54001 q.v. 698 · Zbl 0545.54001 |
| [10] | J. Duparc, Wadge hierarchy and Veblen hierarchy. I. Borel sets of finite rank. J. Symbolic Logic 66 (2001), no. 1, 56-86. MR 1825174 Zbl 0979.03039 q.v. 711, 713, 715 · Zbl 0979.03039 |
| [11] | J. Duparc, A hierarchy of deterministic context-free !-languages. Theoret. Comput. Sci. 290 (2003), no. 3, 1253-1300. MR 1937723 Zbl 1044.68090 q.v. 723 · Zbl 1044.68090 |
| [12] | J. Duparc and F. Murlak, On the topological complexity of weakly recognizable tree lan-guages. In Fundamentals of computation theory (E. Csuhaj-Varjú and Z. Ésik, eds.) Pro-ceedings of the 16 th International Symposium, FCT 2007, Budapest, August 27-30, 2007. Lecture Notes in Computer Science, 4639. Springer, Berlin, 2007, 27-30. Zbl 1135.68028 q.v. 725 · Zbl 1135.68028 |
| [13] | J. Duparc and M. Riss, The missing link for !-rational sets, automata, and semigroups. Internat. J. Algebra Comput. 16 (2006), no. 1, 161-185. MR 2217647 Zbl 1094.68049 q.v. 721, 722 · Zbl 1094.68049 |
| [14] | O. Finkel, An e ective extension of the Wagner hierarchy to blind counter automata. In Computer science logic (L. Fribourg, ed.). Proceedings of the 15 th International Workshop (CSL 2001) held at the Annual Conference of the European Association for Computer Science Logic (EACSL) in Paris, September 10-13, 2001. Lecture Notes in Computer Science, 2142. Springer, Berlin, 2001, 369-383. MR 1908784 Zbl 0999.03034 q.v. 723 · Zbl 0999.03034 |
| [15] | O. Finkel, Borel ranks and Wadge degrees of context free !-languages. Math. Structures Comput. Sci. 16 (2006), no. 5, 813-840. MR 2268344 Zbl 1121.03047 q.v. 723 · Zbl 1121.03047 |
| [16] | O. Finkel, Wadge degrees of infinitary rational relations. Math. Comput. Sci. 2 (2008), no. 1, 85-102. MR 2465283 Zbl 1157.03017 q.v. 724 · Zbl 1157.03017 |
| [17] | O. Finkel, The complexity of infinite computations in models of set theory. Log. Methods Comput. Sci. 5 (2009), no. 4, 4:4, 19 pp. MR 2575076 Zbl 1191.03034 q.v. 723 · Zbl 1191.03034 |
| [18] | O. Finkel, Some problems in automata theory which depend on the models of set theory. RAIRO Theor. Inform. Appl. 45 (2011), no. 4, 383-397. MR 2876113 Zbl 1232.68082 q.v. 723 · Zbl 1232.68082 |
| [19] | O. Finkel, Topological complexity of context-free !-languages: A survey. In Language, culture, computation (N. Dershowitz and E. Nissan, ed.). Computing -theory and tech-nology. Essays dedicated to Yaacov Choueka on the occasion of his 75 th birthday. Part I. Lecture Notes in Computer Science, 8001. Springer, Berlin, 50-77. q.v. 723 · Zbl 1302.68011 |
| [20] | O. Finkel, D. Lecomte, and P. Simonnet, An upper bound on the complexity of recogniz-able tree languages. RAIRO Theor. Inform. Appl. 49 (2015), no. 2, 121-137. MR 3373811 Zbl 1373.03066 q.v. 725 · Zbl 1373.03066 |
| [21] | D. Gale and F. M. Stewart, Infinite games with perfect information. In Contributions to the theory of games (H. W. Kuhn and A. W. Tucker, eds.) Vol. 2. Annals of Mathemat-ics Studies, 28. Princeton University Press, Princeton, N.J., 1953, 245-266. MR 0054922 Zbl 0050.14305 q.v. 703 · Zbl 0050.14305 |
| [22] | S. Hummel and M. Skrzypczak, The topological complexity of MSO+U and related autom-ata models. Fund. Inform. 119 (2012), no. 1, 87-111. MR 2985579 Zbl 1260.03075 q.v. 702 19. Wadge-Wagner hierarchies · Zbl 1260.03075 |
| [23] | J. Jayne and C. Rogers, First level Borel functions and isomorphisms. J. Math. Pures Appl. (9) 61 (1982), no. 2, 177-205. MR 0673304 Zbl 0514.54026 q.v. 705 · Zbl 0514.54026 |
| [24] | T. Jech, Set theory. The third millennium edition, revised and expanded. Springer Mono-graphs in Mathematics. Springer, Berlin, 2003. MR 1940513 Zbl 1007.03002 q.v. 695, 696, 698 · Zbl 1007.03002 |
| [25] | A. S. Kechris, Classical descriptive set theory. Graduate Texts in Mathematics, 156. Springer, New York, 1995. MR 1321597 Zbl 0819.04002 q.v. 698, 703, 704 · Zbl 0819.04002 |
| [26] | K. Kunen, Set theory. An introduction to independence proofs. Studies in Logic and the Foundations of Mathematics, 102. North-Holland Publishing Co., Amsterdam and New York, 1980. MR 0597342 Zbl 0443.03021 q.v. 695, 696 · Zbl 0443.03021 |
| [27] | H. Lebesgue, Sur les fonctions représentables analytiquement. J. Math. Pures Appl. (6) 1 (1905), 139-216. JFM 36.0453.02 q.v. 702 · JFM 36.0453.02 |
| [28] | A. Louveau, Some results in the Wadge hierarchy of Borel sets. In Cabal seminar 79-81 (A. S. Kechris, D. A. Martin, and Y. N. Moschovakis, eds.). Proceedings of the Caltech-UCLA logic seminar held during the academic years 1979-1981. Lecture Notes in Mathe-matics, 1019. Springer, Berlin, 1983, 79-81. MR 0730585 Zbl 0535.03026 q.v. 696, 708 |
| [29] | A. Louveau and J. Saint-Raymond, The strength of Borel Wadge determinacy. In Ca-bal Seminar 81-85 (A. S. Kechris, D. A. Martin, and J. R. Steel, eds.). Proceedings of the Caltech-UCLA logic seminar held during the academic years 1981-1985. Lecture Notes in Mathematics, 1333. Springer, Berlin, 1988, 1-30. MR 0960893 Zbl 1242.03070 q.v. 706 |
| [30] | D. A. Martin, The Wadge degrees are well ordered. Handwritten notes, 1973. q.v. 707 |
| [31] | D. A. Martin, Borel determinacy. Ann. of Math. (2) 102 (1975), no. 2, 363-371. MR 0403976 Zbl 0336.02049 q.v. 704 · Zbl 0336.02049 |
| [32] | D. A. Martin, A purely inductive proof of Borel determinacy. In Recursion theory (A. Nerode and R. A. Shore, eds.). Proceedings of the AMS-ASL summer institute held in Ithaca, N.Y., June 28-July 16, 1982. Proceedings of Symposia in Pure Mathematics, 42. American Mathematical Society, Providence, R.I., 1985, 303-308. MR 0791065 Zbl 0614.03048 q.v. 704 · Zbl 0614.03048 |
| [33] | Y. N. Moschovakis, Notes on set theory. Second edition. Undergraduate Texts in Mathe-matics. Springer, New York, 2006. MR 2192215 Zbl 1088.03003 q.v. 696 · Zbl 1088.03003 |
| [34] | Y. N. Moschovakis, Descriptive set theory. Second edition. Mathematical Surveys and Monographs, 155. American Mathematical Society, Providence, R.I., 2009. MR 2526093 Zbl 1172.03026 q.v. 698, 703, 723 · Zbl 1172.03026 |
| [35] | F. Murlak, On deciding topological classes of deterministic tree languages. In Computer science logic (C.-H. L. Ong, ed.). Proceedings of the 19 th International Workshop (CSL 2005), the 14 th Annual Conference of the EACSL, held at the University of Oxford, Oxford, August 22-25, 2005. Lecture Notes in Computer Science, 3634. Springer, Berlin, 2005, 428-441. MR 2200574 Zbl 1136.03320 q.v. 725 · Zbl 1136.03320 |
| [36] | F. Murlak, The Wadge hierarchy of deterministic tree languages. Log. Methods Comput. Sci. 2008/09, Special issue: Conference “International Colloquium on Automata, Lan-guages and Programming 2006”, 4:15, 44 pp. MR 2734717 Zbl 1159.03025 q.v. 725 · Zbl 1159.03025 |
| [37] | D. Niwiński and I. Walukiewicz, A gap property of deterministic tree languages. Theo-ret. Comput. Sci. 303 (2003), no. 1, 215-231. Logic and complexity in computer science (Créteil, 2001). MR 1990749 Zbl 1044.68120 q.v. 724 · Zbl 1044.68120 |
| [38] | D. Perrin and J.-É. Pin, Infinite words. Automata, semigroups, logic and games. Pure and Applied Mathematics (Amsterdam), 141. Elsevier/Academic Press, 2004. Zbl 1094.68052 q.v. 721 · Zbl 1094.68052 |
| [39] | L. M. Ros and B. Semmes, A new proof of a theorem of Jayne and Rogers. Real Anal. Exchange 35 (2010), no. 1, 195-203. MR 2657295 Zbl 1217.03032 q.v. 705 · Zbl 1217.03032 |
| [40] | V. Selivanov, Fine hierarchy of regular !-languages. Theoret. Comput. Sci. 191 (1998), no. 1-2, 37-59. MR 1490562 Zbl 0908.68085 q.v. 696 · Zbl 0908.68085 |
| [41] | V. Selivanov, Wadge degrees of !-languages of deterministic turing machines. Theor. Inform. Appl. 37 (2003), no. 1, 67-83. MR 1991752 Zbl 1048.03031 q.v. 724 · Zbl 1036.03033 |
| [42] | P. Simonnet, Automate et théorie descriptive. Ph.D. Thesis. Université Paris 7, Paris, 1992. q.v. 715 |
| [43] | M. Skrzypczak, Descriptive set theoretic methods in automata theory Decidability and topological complexity. Dissertation, University of Warsaw, Warsaw. Lecture Notes in Computer Science, 9802. Springer, Berlin, 2016. MR 3534821 Zbl 1375.03003 q.v. 725 · Zbl 1375.03003 |
| [44] | M. Souslin, Sur une définition des ensembles mesurables B sans nombres transfinis. C. R. Acad. Sci. Paris 164 (1917), 88-91. Zbl 46.0296.01 q.v. 702 · JFM 46.0296.01 |
| [45] | R. A. Van Wesep, Separation principles and the axiom of determinateness. J. Symbolic Logic 43 (1978), no. 1, 77-81. MR 0495119 Zbl 0396.03042 q.v. 707 · Zbl 0396.03042 |
| [46] | R. A. Van Wesep, Wadge degrees and descriptive set theory. In Cabal seminar 76-77 (A. S. Kechris and Y. N. Moschovakis, eds.). Proceedings of the Caltech-UCLA logic sem-inar held during the academic years 1976-1977. Lecture Notes in Mathematics, 689. Springer, Berlin, 1978, 151-170. MR 0526917 Zbl 0393.03037 q.v. 707, 708 |
| [47] | W. Wadge, Reducibility and determinateness on the Baire space. Ph.D. thesis. University of California, Berkeley, 1983. q.v. 706, 707, 711, 713 |
| [48] | K. W. Wagner, On !-regular sets. Inform. and Control 43 (1979), no. 2, 123-177. MR 0553694 Zbl 0434.68061 q.v. 715, 718 · Zbl 0434.68061 |
| [49] | T. Wilke, An Eilenberg theorem for 1-languages. In Automata, languages and program-ming (J. L. Albert, B. Monien, and M. Rodríguez-Artalejo, eds.) Proceedings of the Eigh-teenth International Colloquium held at the Universidad Complutense de Madrid, Madrid, July 8-12, 1991. Lecture Notes in Computer Science, 510. Springer, Berlin, 1991, 588-599. MR 1129938 Zbl 0766.68083 q.v. 721 · Zbl 0766.68083 |
| [50] | T. Wilke and H. Yoo, Computing the Wadge degree, the Lifschitz degree, and the Rabin index of a regular language of infinite words in polynomial time. In TAPSOFT’95: Theory and practice of software development. (P. D. Mosses, M. Nielsen, and M. I. Schwartzbach, eds.). Proceedings of the 6 th International Joint Conference on the Theory and Prac-tice of Software Development (CAAP/FASE) held at the University of Aarhus, Aarhus, May 22-26, 1995. Lecture Notes in Computer Science, 915. Springer, Berlin, 1995, 288-302. q.v. 719 · Zbl 1496.68183 |
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.
