The algebraic study of formal languages shows that -rational sets correspond precisely to the -languages recognizable by finite -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 -rational language to the -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 -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 and height .
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}, mrnumber = {2541207}, zbl = {1175.03021}, language = {en}, url = {http://archive.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 SP - 443 EP - 461 VL - 43 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2009004/ DO - 10.1051/ita/2009004 LA - en ID - ITA_2009__43_3_443_0 ER -
%0 Journal Article %A Cabessa, Jérémie %A Duparc, Jacques %T A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : part I %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2009 %P 443-461 %V 43 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2009004/ %R 10.1051/ita/2009004 %G en %F ITA_2009__43_3_443_0
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://archive.numdam.org/articles/10.1051/ita/2009004/
[1] Equivalence between Wadge and Lipschitz determinacy. Ann. Pure Appl. Logic 123 (2003) 163-192. | MR | Zbl
,[2] 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 | Zbl
and ,[3] Chains and superchains for -rational sets, automata and semigroups. Int. J. Algebra Comput. 7 (1997) 673-695. | MR | Zbl
and ,[4] The Wadge-Wagner hierarchy of -rational sets. In Automata, languages and programming (Bologna, 1997). Lect. Notes Comput. Sci. 1256 (1997) 17-35. | MR
and ,[5] The Wagner hierarchy. Int. J. Algebra Comput. 9 (1999) 597-620. | MR | Zbl
and ,[6] Wadge hierarchy and Veblen hierarchy. I. Borel sets of finite rank. J. Symbolic Logic 66 (2001) 56-86. | MR | Zbl
,[7] The missing link for -rational sets, automata, and semigroups. Int. J. Algebra Comput. 16 (2006) 161-185. | MR | Zbl
and ,[8] Application of model theoretic games to discrete linear orders and finite automata. Inform. Control 33 (1977) 281-303. | MR | Zbl
,[9] Borel determinacy. Ann. Math. 102 (1975) 363-371. | MR | Zbl
,[10] R.t McNaughton and S.A. Papert, Counter-Free Automata (M.I.T. research monograph No. 65). The MIT Press (1971). | MR | Zbl
[11] First-order logic and star-free sets. J. Comput. System Sci. 32 (1986) 393-406. | MR | Zbl
and ,[12] Semigroups and automata on infinite words. In Semigroups, formal languages and groups (York, 1993). Kluwer Acad. Publ., Dordrecht (1995) 49-72. | MR | Zbl
and ,[13] Infinite words. Pure and Applied Mathematics 141, Elsevier (2004). | Zbl
and ,[14] Logic, semigroups and automata on words. Ann. Math. Artif. Intell. 16 (1996) 343-384. | MR | Zbl
,[15] 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 | Zbl
,[16] Monoïdes pointés. Semigroup Forum 18 (1979) 235-264. | Zbl
,[17] On finite monoids having only trivial subgroups. Inform. Control 8 (1965) 190-194. | MR | Zbl
,[18] Fine hierarchy of regular -languages. Theoret. Comput. Sci. 191 (1998) 37-59. | MR | Zbl
,[19] Star-free regular sets of -sequences. Inform. Control 42 (1979) 148-156. | MR | Zbl
,[20] Degrees of complexity of subsets of the baire space. Notice A.M.S. (1972) A714-A715.
,[21] Reducibility and determinateness on the Baire space. Ph.D. thesis, University of California, Berkeley (1983).
,[22] On -regular sets. Inform. Control 43 (1979) 123-177. | MR | Zbl
,[23] An Eilenberg theorem for -languages. In Automata, languages and programming (Madrid, 1991). Lect. Notes Comput. Sci. 510 (1991) 588-599. | MR | Zbl
,[24] 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.
and ,Cité par Sources :