# 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

## 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 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- 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 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. Zbl0917.20054
- 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 Wagner hierarchy. Int. J. Algebra Comput.9 (1999) 597–620. Zbl1056.68547
- J. Duparc, Wadge hierarchy and Veblen hierarchy. Part I: Borel sets of finite rank. J. Symbolic Logic66 (2001) 56–86. Zbl0979.03039
- J. Duparc, A hierarchy of deterministic context-free ω>-languages. Theoret. Comput. Sci.290 (2003) 1253–1300. Zbl1044.68090
- J. Duparc, Wadge hierarchy and Veblen hierarchy. Part II: Borel sets of infinite rank (to appear). 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
- 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.
- 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. Zbl1112.03314
- A.S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics156. Springer-Verlag, New York (1995). Zbl0819.04002
- K. Kunen, Set theory. An introduction to independence proofs. 2nd print. Studies in Logic and the Foundations of Mathematics 102. North-Holland (1983) 313. Zbl0534.03026
- R.E. Ladner, Application of model theoretic games to discrete linear orders and finite automata. Inform. Control33 (1977) 281–303. Zbl0387.68037
- Y.N. Moschovakis, Descriptive set theory. Studies in Logic and the Foundations of Mathematics 100. North-Holland Publishing Company (1980) 637.
- 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.-Éric Pin, Infinite words. Pure Appl. Mathematics141. Elsevier (2004). Zbl1094.68052
- J.-E. Pin, Varieties of formal languages. North Oxford, London and Plenum, New-York (1986).
- 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, 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 Peter D. Mosses, M. Nielsen, 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.