# A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I

Jérémie Cabessa; Jacques Duparc

RAIRO - Theoretical Informatics and Applications (2009)

- Volume: 43, Issue: 3, page 443-461
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCabessa, Jérémie, and Duparc, Jacques. "A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I." RAIRO - Theoretical Informatics and Applications 43.3 (2009): 443-461. <http://eudml.org/doc/250579>.

@article{Cabessa2009,

abstract = {
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 2 and height ωω.
},

author = {Cabessa, Jérémie, Duparc, Jacques},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {ω-automata; ω-rational languages; ω-semigroups; infinite games; hierarchical games; Wadge game; Wadge hierarchy; Wagner hierarchy.; -automata; -rational languages; -semigroups; Wagner hierarchy},

language = {eng},

month = {3},

number = {3},

pages = {443-461},

publisher = {EDP Sciences},

title = {A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I},

url = {http://eudml.org/doc/250579},

volume = {43},

year = {2009},

}

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

DA - 2009/3//

PB - EDP Sciences

VL - 43

IS - 3

SP - 443

EP - 461

AB -
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 2 and height ωω.

LA - eng

KW - ω-automata; ω-rational languages; ω-semigroups; infinite games; hierarchical games; Wadge game; Wadge hierarchy; Wagner hierarchy.; -automata; -rational languages; -semigroups; Wagner hierarchy

UR - http://eudml.org/doc/250579

ER -

## References

top- A. Andretta, Equivalence between Wadge and Lipschitz determinacy. Ann. Pure Appl. Logic123 (2003) 163–192. Zbl1024.03053
- 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 Logic11, College Publications, London (2007) 63–78. Zbl1157.20040
- O. Carton and D. Perrin, Chains and superchains for ω-rational sets, automata and semigroups. Int. J. Algebra Comput.7 (1997) 673–695. Zbl0911.68143
- O. Carton and D. Perrin, The Wadge-Wagner hierarchy of ω-rational sets. In Automata, languages and programming (Bologna, 1997). Lect. Notes Comput. Sci.1256 (1997) 17–35.
- O. Carton and D. Perrin, The Wagner hierarchy. Int. J. Algebra Comput.9 (1999) 597–620. Zbl1056.68547
- J. Duparc, Wadge hierarchy and Veblen hierarchy. I. Borel sets of finite rank. J. Symbolic Logic66 (2001) 56–86. Zbl0979.03039
- J. Duparc and M. Riss, The missing link for ω-rational sets, automata, and semigroups. Int. J. Algebra Comput.16 (2006) 161–185. Zbl1094.68049
- R.E. Ladner, Application of model theoretic games to discrete linear orders and finite automata. Inform. Control33 (1977) 281–303. Zbl0387.68037
- D.A. Martin, Borel determinacy. Ann. Math.102 (1975) 363–371.
- R.t McNaughton and S.A. Papert, Counter-Free Automata (M.I.T. research monograph No. 65). The MIT Press (1971). Zbl0232.94024
- D. Perrin and J.-E. Pin, First-order logic and star-free sets. J. Comput. System Sci.32 (1986) 393–406. Zbl0618.03015
- 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. Zbl0877.20045
- D. Perrin and J.-E. Pin, Infinite words. Pure and Applied Mathematics141, Elsevier (2004). Zbl1094.68052
- J.-E. Pin, Logic, semigroups and automata on words. Ann. Math. Artif. Intell.16 (1996) 343–384.
- 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. Zbl0909.20051
- J. Sakarovitch, Monoïdes pointés. Semigroup Forum18 (1979) 235–264. Zbl0419.68093
- M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. Control8 (1965) 190–194. Zbl0131.02001
- V. Selivanov, Fine hierarchy of regular ω-languages. Theoret. Comput. Sci.191 (1998) 37–59. Zbl0908.68085
- W. Thomas, Star-free regular sets of ω-sequences. Inform. Control42 (1979) 148–156. Zbl0411.03031
- W.W. Wadge, Degrees of complexity of subsets of the baire space. Notice A.M.S. (1972) A714–A715.
- W.W. Wadge, Reducibility and determinateness on the Baire space. Ph.D. thesis, University of California, Berkeley (1983).
- K. Wagner, On ω-regular sets. Inform. Control43 (1979) 123–177. Zbl0434.68061
- T. Wilke, An Eilenberg theorem for ∞-languages. In Automata, languages and programming (Madrid, 1991). Lect. Notes Comput. Sci.510 (1991) 588–599. Zbl0766.68083
- 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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.