Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
In this paper, we first introduce a lower bound technique for the state complexity of transformations of automata. Namely we suggest first considering the class of full automata in lower bound analysis, and later reducing the size of the large alphabet via alphabet substitutions. Then we apply such technique to …