A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : part II

Cabessa, Jérémie; Duparc, Jacques

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009), p. 463-515 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

The algebraic counterpart of the Wagner hierarchy consists of a well-founded and decidable classification of finite pointed $ω$ -semigroups of width $2$ and height $ω^{ω}$ . This paper completes the description of this algebraic hierarchy. We first give a purely algebraic decidability procedure of this partial ordering by introducing a graph representation of finite pointed $ω$ -semigroups allowing to compute their precise Wagner degrees. The Wagner degree of any $ω$ -rational language can therefore be computed directly on its syntactic image. We then show how to build a finite pointed $ω$ -semigroup of any given Wagner degree. We finally describe the algebraic invariants characterizing every degree of this hierarchy.

Publié le : 2009-01-01

MR 2541208 | Zbl 1175.03022

DOI : https://doi.org/10.1051/ita/2009007
Classification: O3D55, 20M35, 68Q70, 91A65

@article{ITA_2009__43_3_463_0,
     author = {Cabessa, J\'er\'emie and Duparc, Jacques},
     title = {A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : part II},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {43},
     year = {2009},
     pages = {463-515},
     doi = {10.1051/ita/2009007},
     mrnumber = {2541208},
     zbl = {1175.03022},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2009__43_3_463_0}
}

Cabessa, Jérémie; Duparc, Jacques. A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : part II. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) pp. 463-515. doi : 10.1051/ita/2009007. http://gdmltest.u-ga.fr/item/ITA_2009__43_3_463_0/

Bibliographie

[1] J. Cabessa and J. Duparc, An infinite game over $ω$ -semigroups, in Foundations of the Formal Sciences V, Infinite Games, edited by S. Bold, B. Löwe, T. Räsch, J. van Benthem. Studies in Logic 11. College Publications, London (2007) 63-78. | MR 2427616 | Zbl 1157.20040

[2] O. Carton and D. Perrin, Chains and superchains in $ω$ -semigroups, edited by Almeida Jorge et al., Semigroups, automata and languages. Papers from the conference, Porto, Portugal (1994) June 20-24. World Scientific, Singapore (1996) 17-28. | MR 1477719 | Zbl 0917.20054

[3] O. Carton and D. Perrin, Chains and superchains for $ω$ -rational sets, automata and semigroups. Int. J. Algebra Comput. 7 (1997) 673-695. | MR 1482963 | Zbl 0911.68143

[4] O. Carton and D. Perrin, The Wagner hierarchy. Int. J. Algebra Comput. 9 (1999) 597-620. | MR 1719703 | Zbl 1056.68547

[5] J. Duparc, Wadge hierarchy and Veblen hierarchy. Part I: Borel sets of finite rank. J. Symbolic Logic 66 (2001) 56-86. | MR 1825174 | Zbl 0979.03039

[6] J. Duparc, A hierarchy of deterministic context-free $ω$ -languages. Theoret. Comput. Sci. 290 (2003) 1253-1300. | MR 1937723 | Zbl 1044.68090

[7] J. Duparc, Wadge hierarchy and Veblen hierarchy. Part II: Borel sets of infinite rank (to appear). | Zbl 0979.03039

[8] J. Duparc and M. Riss, The missing link for $ω$ -rational sets, automata, and semigroups. Int. J. Algebra Comput. 16 (2006) 161-185. | Zbl 1094.68049

[9] O. Finkel, An effective extension of the Wagner hierarchy to blind counter automata. In Computer Science Logic (Paris, 2001); Lect. Notes Comput. Sci. 2142 (2001) 369-383. | Zbl 0999.03034

[10] O. Finkel, Borel ranks and Wadge degrees of context free omega languages. In New Computational Paradigms, First Conference on Computability in Europe, CiE. Lect. Notes Comput. Sci. 2142 (2005) 129-138. | Zbl 1112.03314

[11] A.S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics 156. Springer-Verlag, New York (1995). | Zbl 0819.04002

[12] K. Kunen, Set theory. An introduction to independence proofs. 2nd print. Studies in Logic and the Foundations of Mathematics 102. North-Holland (1983) 313. | Zbl 0534.03026

[13] R.E. Ladner, Application of model theoretic games to discrete linear orders and finite automata. Inform. Control 33 (1977) 281-303. | MR 491116 | Zbl 0387.68037

[14] Y.N. Moschovakis, Descriptive set theory. Studies in Logic and the Foundations of Mathematics 100. North-Holland Publishing Company (1980) 637. | MR 561709 | Zbl 0433.03025

[15] D. Perrin and J.-E. Pin, First-order logic and star-free sets. J. Comput. System Sci. 32 (1986) 393-406. | MR 858236 | Zbl 0618.03015

[16] D. Perrin and J.-Éric Pin, Infinite words. Pure Appl. Mathematics 141. Elsevier (2004). | Zbl 1094.68052

[17] J.-E. Pin, Varieties of formal languages. North Oxford, London and Plenum, New-York (1986). | MR 912694 | Zbl 0632.68069

[18] V. Selivanov, Fine hierarchy of regular $ω$ -languages. Theoret. Comput. Sci. 191 (1998) 37-59. | MR 1490562 | Zbl 0908.68085

[19] W. Thomas, Star-free regular sets of $ω$ -sequences. Inform. Control 42 (1979) 148-156. | MR 542328 | Zbl 0411.03031

[20] W.W. Wadge, Reducibility and determinateness on the Baire space. Ph.D. thesis, University of California, Berkeley (1983).

[21] K. Wagner, On $ω$ -regular sets. Inform. Control 43 (1979) 123-177. | MR 553694 | Zbl 0434.68061

[22] T. Wilke, An Eilenberg theorem for $\infty$ -languages. In Automata, languages and programming (Madrid, 1991). Lect. Notes Comput. Sci. 510 (1991) 588-599. | MR 1129938 | Zbl 0766.68083

[23] T. Wilke and H. Yoo, Computing the Wadge degree, the Lifshitz degree, and the Rabin index of a regular language of infinite words in polynomial time. In TAPSOFT '95: Theory and Practive of Software Development, edited by Peter D. Mosses, M. Nielsen, M.I. Schwartzbach. Lect. Notes Comput. Sci. 915 (1995) 288-302.