Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Complexity of aperiodicity for topological properties of regular $\omega$-languages

Edit abstract data

Author(s): Victor Selivanov and Klaus W. Wagner
Slot: Fri, 11:00-11:20, Amphitheater B (col. 2)


We study the complexity of aperiodicity restricted to topological
properties of regular $\omega$-languages (i.e. properties closed
under the Wadge equivalence on the Cantor space of $\omega$-words)
restricted to aperiodic sets. In particular, we show the
PSPACE-completeness of such problems  for several usual
deterministic and non-deterministic automata representations of
regular $\omega$-languages.

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