Computability in Europe 2008
Logic and Theory of Algorithms
|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|