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

Abstract

top
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 ωω.

How to cite

top

Cabessa, 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
  1. A. Andretta, Equivalence between Wadge and Lipschitz determinacy. Ann. Pure Appl. Logic123 (2003) 163–192.  
  2. 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.  
  3. O. Carton and D. Perrin, Chains and superchains for ω-rational sets, automata and semigroups. Int. J. Algebra Comput.7 (1997) 673–695.  
  4. 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.  
  5. O. Carton and D. Perrin, The Wagner hierarchy. Int. J. Algebra Comput.9 (1999) 597–620.  
  6. J. Duparc, Wadge hierarchy and Veblen hierarchy. I. Borel sets of finite rank. J. Symbolic Logic66 (2001) 56–86.  
  7. J. Duparc and M. Riss, The missing link for ω-rational sets, automata, and semigroups. Int. J. Algebra Comput.16 (2006) 161–185.  
  8. R.E. Ladner, Application of model theoretic games to discrete linear orders and finite automata. Inform. Control33 (1977) 281–303.  
  9. D.A. Martin, Borel determinacy. Ann. Math.102 (1975) 363–371.  
  10. R.t McNaughton and S.A. Papert, Counter-Free Automata (M.I.T. research monograph No. 65). The MIT Press (1971).  
  11. D. Perrin and J.-E. Pin, First-order logic and star-free sets. J. Comput. System Sci.32 (1986) 393–406.  
  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.  
  13. D. Perrin and J.-E. Pin, Infinite words. Pure and Applied Mathematics141, Elsevier (2004).  
  14. J.-E. Pin, Logic, semigroups and automata on words. Ann. Math. Artif. Intell.16 (1996) 343–384.  
  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.  
  16. J. Sakarovitch, Monoïdes pointés. Semigroup Forum18 (1979) 235–264.  
  17. M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. Control8 (1965) 190–194.  
  18. V. Selivanov, Fine hierarchy of regular ω-languages. Theoret. Comput. Sci.191 (1998) 37–59.  
  19. W. Thomas, Star-free regular sets of ω-sequences. Inform. Control42 (1979) 148–156.  
  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 ω-regular sets. Inform. Control43 (1979) 123–177.  
  23. T. Wilke, An Eilenberg theorem for ∞-languages. In Automata, languages and programming (Madrid, 1991). Lect. Notes Comput. Sci.510 (1991) 588–599.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.