RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

Issue		RAIRO-Theor. Inf. Appl. Volume 43, Number 3, July-September 2009
Page(s)		463 - 515
DOI		10.1051/ita/2009007
Published online		12 March 2009

RAIRO-Theor. Inf. Appl. 43, 463-515 (2009)
DOI: 10.1051/ita/2009007

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

Jérémie Cabessa and Jacques Duparc

University of Lausanne, Faculty of Business and Economics, HEC - ISI, 1015 Lausanne, Switzerland; Jeremie.Cabessa@unil.ch

Received April 10, 2008. Accepted December 18, 2008. Published online 12 March 2009

Abstract
The algebraic counterpart of the Wagner hierarchy consists of a well-founded and decidable classification of finite pointed $\omega$ -semigroups of width 2 and height $\omega^\omega$ . 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 $\omega$ -semigroups allowing to compute their precise Wagner degrees. The Wagner degree of any $\omega$ -rational language can therefore be computed directly on its syntactic image. We then show how to build a finite pointed $\omega$ -semigroup of any given Wagner degree. We finally describe the algebraic invariants characterizing every degree of this hierarchy.

Mathematics Subject Classification. O3D55, 20M35, 68Q70, 91A65

Key words: $\omega$ -automata -- $\omega$ -rational languages -- $\omega$ -semigroups -- infinite games -- hierarchical games -- Wadge game -- Wadge hierarchy -- Wagner hierarchy.

© EDP Sciences 2009

What is OpenURL?