Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-27T07:29:24.437Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  12 March 2009

Jérémie Cabessa  and
Jacques Duparc
Jérémie Cabessa
Affiliation:
University of Lausanne, Faculty of Business and Economics, HEC - ISI, 1015 Lausanne, Switzerland; [email protected]
Jacques Duparc
Affiliation:
University of Lausanne, Faculty of Business and Economics, HEC - ISI, 1015 Lausanne, Switzerland; [email protected]
Get access

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.

Keywords

ω-automataω-rational languagesω-semigroupsinfinite gameshierarchical gamesWadge gameWadge hierarchyWagner hierarchy.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 43 , Issue 3 , July 2009 , pp. 463 - 515
Copyright
© EDP Sciences, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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 Logic 11. College Publications, London (2007) 63–78.
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.
Carton, O. and Perrin, D., Chains and superchains for ω-rational sets, automata and semigroups. Int. J. Algebra Comput. 7 (1997) 673–695. CrossRef
Carton, O. and Perrin, D., The Wagner hierarchy. Int. J. Algebra Comput. 9 (1999) 597–620. CrossRef
Duparc, J., Wadge hierarchy and Veblen hierarchy. Part I: Borel sets of finite rank. J. Symbolic Logic 66 (2001) 56–86. CrossRef
Duparc, J., A hierarchy of deterministic context-free ω>-languages. Theoret. Comput. Sci. 290 (2003) 1253–1300. CrossRef
J. Duparc, Wadge hierarchy and Veblen hierarchy. Part II: Borel sets of infinite rank (to appear).
Duparc, J. and Riss, M., The missing link for ω-rational sets, automata, and semigroups. Int. J. Algebra Comput. 16 (2006) 161–185. CrossRef
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.
Finkel, O., 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. CrossRef
A.S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics 156. Springer-Verlag, New York (1995).
K. Kunen, Set theory. An introduction to independence proofs. 2nd print. Studies in Logic and the Foundations of Mathematics 102. North-Holland (1983) 313.
Ladner, R.E., Application of model theoretic games to discrete linear orders and finite automata. Inform. Control 33 (1977) 281–303. CrossRef
Y.N. Moschovakis, Descriptive set theory. Studies in Logic and the Foundations of Mathematics 100. North-Holland Publishing Company (1980) 637.
Perrin, D. and Pin, J.-E., First-order logic and star-free sets. J. Comput. System Sci. 32 (1986) 393–406. CrossRef
D. Perrin and J.-Éric Pin, Infinite words. Pure Appl. Mathematics 141. Elsevier (2004).
J.-E. Pin, Varieties of formal languages. North Oxford, London and Plenum, New-York (1986).
Selivanov, V., Fine hierarchy of regular ω-languages. Theoret. Comput. Sci. 191 (1998) 37–59. CrossRef
Thomas, W., Star-free regular sets of ω-sequences. Inform. Control 42 (1979) 148–156. CrossRef
W.W. Wadge, Reducibility and determinateness on the Baire space. Ph.D. thesis, University of California, Berkeley (1983).
Wagner, K., On ω-regular sets. Inform. Control 43 (1979) 123–177. CrossRef
Wilke, T., Eilenberg, An theorem for ∞-languages. In Automata, languages and programming (Madrid, 1991). Lect. Notes Comput. Sci. 510 (1991) 588–599. CrossRef
Wilke, T. and Yoo, H., 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. CrossRef