  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 the complementation of nondeterministic \omega-automata, and obtain several
lower bound results. Particularly, we prove an \omega((0.76n)^n) lower bound
for B\"uchi complementation, which also holds for almost every complementation
or determinization transformation of nondeterministic omega-automata, and prove
an optimal (\omega(nk))^n lower bound for the complementation of generalized
B\"uchi automata, which holds for Streett automata as well.
