Computability in Europe 2006
Logical Approaches to Computational Barriers


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


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

Abstract

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