A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II

Jérémie Cabessa; Jacques Duparc

RAIRO - Theoretical Informatics and Applications (2009)

  • Volume: 43, Issue: 3, page 463-515
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Cabessa, Jérémie, and Duparc, Jacques. "A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II." RAIRO - Theoretical Informatics and Applications 43.3 (2009): 463-515. <http://eudml.org/doc/250608>.

@article{Cabessa2009,
abstract = { 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. },
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 = {463-515},
publisher = {EDP Sciences},
title = {A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II},
url = {http://eudml.org/doc/250608},
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 II
JO - RAIRO - Theoretical Informatics and Applications
DA - 2009/3//
PB - EDP Sciences
VL - 43
IS - 3
SP - 463
EP - 515
AB - 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.
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/250608
ER -

References

top
  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 Logic11. College Publications, London (2007) 63–78.  
  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.  
  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 Wagner hierarchy. Int. J. Algebra Comput.9 (1999) 597–620.  
  5. J. Duparc, Wadge hierarchy and Veblen hierarchy. Part I: Borel sets of finite rank. J. Symbolic Logic66 (2001) 56–86.  
  6. J. Duparc, A hierarchy of deterministic context-free ω>-languages. Theoret. Comput. Sci.290 (2003) 1253–1300.  
  7. J. Duparc, Wadge hierarchy and Veblen hierarchy. Part II: Borel sets of infinite rank (to appear).  
  8. J. Duparc and M. Riss, The missing link for ω-rational sets, automata, and semigroups. Int. J. Algebra Comput.16 (2006) 161–185.  
  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.  
  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.  
  11. A.S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics156. Springer-Verlag, New York (1995).  
  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.  
  13. R.E. Ladner, Application of model theoretic games to discrete linear orders and finite automata. Inform. Control33 (1977) 281–303.  
  14. Y.N. Moschovakis, Descriptive set theory. Studies in Logic and the Foundations of Mathematics 100. North-Holland Publishing Company (1980) 637.  
  15. D. Perrin and J.-E. Pin, First-order logic and star-free sets. J. Comput. System Sci.32 (1986) 393–406.  
  16. D. Perrin and J.-Éric Pin, Infinite words. Pure Appl. Mathematics141. Elsevier (2004).  
  17. J.-E. Pin, Varieties of formal languages. North Oxford, London and Plenum, New-York (1986).  
  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, Reducibility and determinateness on the Baire space. Ph.D. thesis, University of California, Berkeley (1983).  
  21. K. Wagner, On ω-regular sets. Inform. Control43 (1979) 123–177.  
  22. T. Wilke, An Eilenberg theorem for ∞-languages. In Automata, languages and programming (Madrid, 1991). Lect. Notes Comput. Sci.510 (1991) 588–599.  
  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.  

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.