Complexity of Topological Properties of Regular ω-Languages

Article type: Research Article

Authors: Selivanov, Victor L. | Wagner, Klaus W.

Affiliations: A.P. Ershov Institute of Informatics Systems, Siberian Division of the Russian Academy of Sciences, Russia. E-mail: [email protected] and Institut für Informatik, Julius-Maximilians-Universität Würzburg, Germany. E-mail: [email protected]

Abstract: We determine the complexity of topological properties (i.e., properties closed under the Wadge equivalence) of regular ω-languages by showing that they are typically NL-complete (PSPACE-complete) for the deterministic Muller, Mostowski and Büchi automata (respectively, for the nondeterministic Rabin, Muller, Mostowski and Büchi automata). For the deterministic Rabin and Streett automata and for the nondeterministic Streett automata upper and lower complexity bounds for the topological properties are established.

Journal: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 197-217, 2008