理论计算机科学中的若干下界结果

【作者】 严奇琦；

【导师】 沈恩绍；

【作者基本信息】 上海交通大学 ， 计算机软件与理论， 2007， 硕士

【摘要】 本文中，我们对理论计算机科学中的下界问题及其意义进行了简要的综述，并阐述了作者在ω-自动机转换的状态复杂性和形式语言中starheight问题上的两项研究工作。 在ω-自动机转换上，我们首先提出了一种证明自动机状态转换复杂性下界的技巧，即full自动机技巧，然后将这种技巧应用到非确定ω-自动机的求补操作上。具体地，我们证明了一个Buchi自动机求补的Ω((0.76n)~n)的下界，并且证明了这个下界对于几乎所有ω-自动机的求补和确定化操作都有效。我们也证明了一个广义Buchi自动机求补的(Ω(nk))~n的下界，而这个下界对于Streett自动机的求补也有效。该项工作发表在了欧洲顶级的ICALP理论会议上，并获得最佳学生论文奖。 关于star height问题，我们引入了split游戏，一种逻辑中Ehrenfeucht-Fra(?)ssé游戏的变种，并证明了这种游戏能用于分析广义正则表达式的表达能力。我们也把split游戏推广到了广义ω-正则表达式。为了理解这种游戏如何能被用来攻克著名的困难的star height 2问题，我们提出并且解决了star height 2问题在ω-语言理论中的一个类似的但较为容易驾驭的变种，即omega power问题。实际上，我们证明了omega power算子和布尔算子以及连接算子一起无法表达整个ω-正则语言类。这项工作已被著名的Theoretical Computer Science杂志接受。更多还原

【Abstract】 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.更多还原