A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : part I
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 443-461.

The algebraic study of formal languages shows that $\omega$-rational sets correspond precisely to the $\omega$-languages recognizable by finite $\omega$-semigroups. Within this framework, we provide a construction of the algebraic counterpart of the Wagner hierarchy. We adopt a hierarchical game approach, by translating the Wadge theory from the $\omega$-rational language to the $\omega$-semigroup context. More precisely, we first show that the Wagner degree is indeed a syntactic invariant. We then define a reduction relation on finite pointed $\omega$-semigroups by means of a Wadge-like infinite two-player game. The collection of these algebraic structures ordered by this reduction is then proven to be isomorphic to the Wagner hierarchy, namely a well-founded and decidable partial ordering of width $2$ and height ${\omega }^{\omega }$.

DOI : https://doi.org/10.1051/ita/2009004
Classification : O3D55,  20M35,  68Q70,  91A65
Mots clés : $\omega$-automata, $\omega$-rational languages, $\omega$-semigroups, infinite games, hierarchical games, Wadge game, Wadge hierarchy, Wagner hierarchy
@article{ITA_2009__43_3_443_0,
author = {Cabessa, J\'er\'emie and Duparc, Jacques},
title = {A game theoretical approach to the algebraic counterpart of the {Wagner} hierarchy : part {I}},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {443--461},
publisher = {EDP-Sciences},
volume = {43},
number = {3},
year = {2009},
doi = {10.1051/ita/2009004},
zbl = {1175.03021},
mrnumber = {2541207},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2009004/}
}
TY  - JOUR
AU  - Cabessa, Jérémie
AU  - Duparc, Jacques
TI  - A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : part I
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
DA  - 2009///
SP  - 443
EP  - 461
VL  - 43
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2009004/
UR  - https://zbmath.org/?q=an%3A1175.03021
UR  - https://www.ams.org/mathscinet-getitem?mr=2541207
UR  - https://doi.org/10.1051/ita/2009004
DO  - 10.1051/ita/2009004
LA  - en
ID  - ITA_2009__43_3_443_0
ER  - 
Cabessa, Jérémie; Duparc, Jacques. A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : part I. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 443-461. doi : 10.1051/ita/2009004. http://www.numdam.org/articles/10.1051/ita/2009004/

[1] A. Andretta, Equivalence between Wadge and Lipschitz determinacy. Ann. Pure Appl. Logic 123 (2003) 163-192. | MR 1998229 | Zbl 1024.03053

[2] J. Cabessa and J. Duparc, An infinite game over $\omega$-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

[3] O. Carton and D. Perrin, Chains and superchains for $\omega$-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 Wadge-Wagner hierarchy of $\omega$-rational sets. In Automata, languages and programming (Bologna, 1997). Lect. Notes Comput. Sci. 1256 (1997) 17-35. | MR 1616171

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

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

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

[8] 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

[9] D.A. Martin, Borel determinacy. Ann. Math. 102 (1975) 363-371. | MR 403976 | Zbl 0336.02049

[10] R.t McNaughton and S.A. Papert, Counter-Free Automata (M.I.T. research monograph No. 65). The MIT Press (1971). | MR 371538 | Zbl 0232.94024

[11] 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

[12] D. Perrin and J.-E. Pin, Semigroups and automata on infinite words. In Semigroups, formal languages and groups (York, 1993). Kluwer Acad. Publ., Dordrecht (1995) 49-72. | MR 1630618 | Zbl 0877.20045

[13] D. Perrin and J.-E. Pin, Infinite words. Pure and Applied Mathematics 141, Elsevier (2004). | Zbl 1094.68052

[14] J.-E. Pin, Logic, semigroups and automata on words. Ann. Math. Artif. Intell. 16 (1996) 343-384. | MR 1389853 | Zbl 0860.68071

[15] J.-E. Pin, Positive varieties and infinite words. in edited by Latin'98, edited by C.L. Lucchesi and A.V. Moura. Lect. Notes Comput. Sci. 1380 (1998) 76-87. | MR 1635489 | Zbl 0909.20051

[16] J. Sakarovitch, Monoïdes pointés. Semigroup Forum 18 (1979) 235-264. | Zbl 0419.68093

[17] M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. Control 8 (1965) 190-194. | MR 176883 | Zbl 0131.02001

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

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

[20] W.W. Wadge, Degrees of complexity of subsets of the baire space. Notice A.M.S. (1972) A714-A715.

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

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

[23] 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

[24] 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 P.D. Mosses, M. Nielsen and M.I. Schwartzbach. Lect. Notes Comput. Sci. 915 (1995) 288-302.

Cité par Sources :