Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique
verfasst von : Qiqi Yan
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we first introduce a new lower bound technique for the state complexity of transformations of automata. Namely we suggest considering the class of full automata in lower bound analysis. Then we apply such technique to the complementation of nondeterministic
ω
-automata and obtain several lower bound results. Particularly, we prove an Ω((0.76
n
)
n
) lower bound for Büchi complementation, which also holds for almost every complementation and determinization transformation of nondeterministic
ω
-automata, and prove an optimal (Ω(
nk
))
n
lower bound for the complementation of generalized Büchi automata, which holds for Streett automata as well.