test FOO test
Computability in Europe 2006
Logical Approaches to Computational Barriers
(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
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