A GAME THEORETICAL APPROACH TO THE ALGEBRAIC COUNTERPART OF THE WAGNER HIERARCHY: PART I
The algebraic study of formal languages shows that omega-rational sets correspond precisely to the omega-languages recognizable by finite omega-semigroups. Within this framework, we provide a construction of the algebraic counterpart of the Wagner hierarchy. We adopt a hierarchical game approach, by translating the Wadge theory from the omega-rational language to the omega-semigroup context. More precisely, we first show that the Wagner degree is indeed a syntactic invariant. We then define a reduction relation on finite pointed omega-semigroups by means of a Wadge-like infinite two-player game. The collection of these algebraic structures ordered by this reduction is then proven to be isomorphic to the Wagner hierarchy, namely a well-founded and decidable partial ordering of width 2 and height omega(omega).
wagner hierarchy omega-semigroups hierarchical games omega-rational languages omega-automata infinite games wadge game wadge hierarchy