Logical Approaches to Computational Barriers

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 |

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 |