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

Received: 10 April 2008
Accepted: 18 December 2008

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.