A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : part I

Cabessa, Jérémie ; Duparc, Jacques

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 443-461.

Résumé

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 }$.

Détail

DOI : 10.1051/ita/2009004

Classification : O3D55, 20M35, 68Q70, 91A65
Mots-clés : $\omega $-automata, $\omega $-rational languages, $\omega $-semigroups, infinite games, hierarchical games, Wadge game, Wadge hierarchy, Wagner hierarchy