Standard

Complexity of topological properties of regular ω-languages. / Selivanov, Victor L.; Wagner, Klaus W.

In: Fundamenta Informaticae, Vol. 83, No. 1-2, 04.08.2008, p. 197-217.

Research output: Contribution to journal › Article › peer-review

Harvard

Selivanov, VL & Wagner, KW 2008, 'Complexity of topological properties of regular ω-languages', Fundamenta Informaticae, vol. 83, no. 1-2, pp. 197-217.

APA

Selivanov, V. L., & Wagner, K. W. (2008). Complexity of topological properties of regular ω-languages. Fundamenta Informaticae, 83(1-2), 197-217.

Vancouver

Selivanov VL, Wagner KW. Complexity of topological properties of regular ω-languages. Fundamenta Informaticae. 2008 Aug 4;83(1-2):197-217.

Author

Selivanov, Victor L. ; Wagner, Klaus W. / Complexity of topological properties of regular ω-languages. In: Fundamenta Informaticae. 2008 ; Vol. 83, No. 1-2. pp. 197-217.

BibTeX

@article{8cd49b202f7141d492bdbca1aacedb64,
title = "Complexity of topological properties of regular ω-languages",
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{\"u}chi automata (respectively, for the nondeterministic Rabin, Muller, Mostowski and B{\"u}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.",
author = "Selivanov, {Victor L.} and Wagner, {Klaus W.}",
year = "2008",
month = aug,
day = "4",
language = "English",
volume = "83",
pages = "197--217",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "1-2",

}

RIS

TY - JOUR

T1 - Complexity of topological properties of regular ω-languages

AU - Selivanov, Victor L.

AU - Wagner, Klaus W.

PY - 2008/8/4

Y1 - 2008/8/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=48249125884&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:48249125884

VL - 83

SP - 197

EP - 217

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1-2

ER -

ID: 127087902