A GAME THEORETICAL APPROACH TO THE ALGEBRAIC COUNTERPART OF THE WAGNER HIERARCHY: PART II
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.
wagner hierarchy omega-semigroups omega-rational languages omega-automata infinite games hierarchical games wadge game wadge hierarchy