A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II
University of Lausanne, Faculty of Business and Economics, HEC - ISI, 1015 Lausanne, Switzerland; Jeremie.Cabessa@unil.ch
Accepted: 18 December 2008
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.
Mathematics Subject Classification: O3D55 / 20M35 / 68Q70 / 91A65
Key words: ω-automata / ω-rational languages / ω-semigroups / infinite games / hierarchical games / Wadge game / Wadge hierarchy / Wagner hierarchy.
© EDP Sciences, 2009