Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
The Algebraic Counterpart of the Wagner Hierarchy

Edit abstract data

Author(s): Jérémie Cabessa and Jacques Duparc
Slot: Fri, 11:20-11:40, Amphitheater B (col. 2)


(TBA)The algebraic study of formal languages shows that $\omega$-rational languages are exactly the sets recognizable by finite $\omega$-semi\-groups. 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 define a reduction relation on finite pointed $\omega$-semi\-groups 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 decidable and well-founded partial ordering of width 2 and height $\omega^\omega$.

websites: Arnold Beckmann 2008-05-18 Valid HTML 4.01! Valid CSS!