Theoretical Computer Science, A Number Of Lower Bound Results

In this thesis, we first present a short survey on the lower bound problems in theoretical computer science, and their significance. Then we present two of our original works in this aspect, one on the state complexity of transforming ω-automata, and the other on the (generalized) star height problem.On transforming ω-automata, we first introduce the full automata technique, which is helpful for analyzing the state complexity of transformations of automata. Namely we suggest to first consider the class of full automata in lower bound analysis, and later reduce the size of the large alphabet via alphabet substitutions. 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 Buchi 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 Buchi automata, which holds for Streett automata as well. This work has been published in ICALP'06, the top European theory conference, and won the best student paperaward.On the star height problem, we introduce the split game, a variant of the Ehrenfeucht-Frai|¨ssé game from logic, which is useful for analyzing the expressive power of classes of generalized regular expressions. An extension of the split game to generalized ω-regular expressions is also established. To gain insight into how the split game can be applied to attack the long-standing generalized star height 2 problem, we propose and solve the omega power problem, a similar but tractable problem in the context of ω-languages. Namely we show that omega powers, together with boolean combinations and concatenations, are not sufficient to express the class of ω-regular languages. This work has been accepted by the prestigious journal Theoretical Computer Science.