Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique

摘要

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.76n)~n) lower bound for Buechi 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 Buechi automata, which holds for Streett automata as well.