A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I
University of Lausanne, Faculty of Business and Economics, HEC - ISI, 1015 Lausanne, Switzerland; Jeremie.Cabessa@unil.ch
Accepted: 18 December 2008
The algebraic study of formal languages shows that ω-rational sets correspond precisely to the ω-languages recognizable by finite ω-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 ω-rational language to the ω-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 ω-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 ωω.
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