RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

Issue		RAIRO-Theor. Inf. Appl. Volume 43, Number 3, July-September 2009
Page(s)		443 - 461
DOI		10.1051/ita/2009004
Published online		06 March 2009

RAIRO-Theor. Inf. Appl. 43, 443-461 (2009)
DOI: 10.1051/ita/2009004

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

Jérémie Cabessa and Jacques Duparc

University of Lausanne, Faculty of Business and Economics, HEC - ISI, 1015 Lausanne, Switzerland; Jeremie.Cabessa@unil.ch

Received Avril 10, 2008. Accepted December 18, 2008. Published online 6 March 2009

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

Mathematics Subject Classification. O3D55, 20M35, 68Q70, 91A65

Key words: $\omega$ -automata -- $\omega$ -rational languages -- $\omega$ -semigroups -- infinite games -- hierarchical games -- Wadge game -- Wadge hierarchy -- Wagner hierarchy.

© EDP Sciences 2009

What is OpenURL?