| 摘要 | 第1-6页 |
| ABSTRACT(英文摘要) | 第6-9页 |
| 第一章 理论计算机科学中下界问题的简要综述 | 第9-14页 |
| ·下界问题及其意义 | 第9-11页 |
| ·翻煎饼问题 | 第9页 |
| ·抽象的数学描述 | 第9-10页 |
| ·复杂性度量 | 第10页 |
| ·上界问题 | 第10-11页 |
| ·下界问题及其意义 | 第11页 |
| ·一些典型的下界问题领域 | 第11-14页 |
| ·自动机转换的状态复杂性 | 第11-12页 |
| ·形式语言中的下界问题 | 第12页 |
| ·电路复杂性 | 第12页 |
| ·算法的下界分析 | 第12-13页 |
| ·小结 | 第13-14页 |
| 第二章 ω-自动机求补操作的下界研究 | 第14-36页 |
| ·简介 | 第14-15页 |
| ·Full自动机和Sakoda-Sipser语言 | 第15页 |
| ·一些基本定义 | 第15-17页 |
| ·Full自动机技巧 | 第17-21页 |
| ·Büchi自动机的求补操作 | 第21-28页 |
| ·Kupferman-Vardi构造 | 第21-23页 |
| ·下界证明 | 第23-26页 |
| ·小字符集的情况 | 第26-28页 |
| ·其他转换操作 | 第28页 |
| ·广义Büchi自动机的求补操作: | 第28-35页 |
| ·标准广义Full Büchi自动机FB_(n,k) | 第29页 |
| ·Michel的技巧的一种推广 | 第29-31页 |
| ·FB_(n,k)的一个冲突集 | 第31-34页 |
| ·下界结果 | 第34-35页 |
| ·小结 | 第35-36页 |
| 第三章 基于split游戏的对正规语言分类的方法 | 第36-53页 |
| ·简介 | 第36-37页 |
| ·相关工作 | 第37页 |
| ·正则表达式与正则表达式类 | 第37-39页 |
| ·split游戏 | 第39-41页 |
| ·split游戏应用的简单例子 | 第41-43页 |
| ·一种到ω正则语言情形的推广 | 第43-44页 |
| ·Omega Power问题 | 第44-53页 |
| ·问题的引入 | 第44-45页 |
| ·证明 | 第45-53页 |
| ·规范的ω-分割 | 第46-47页 |
| ·Jumping自动机 | 第47-48页 |
| ·赢取(ω,n)-游戏 | 第48-53页 |
| 结论 | 第53-54页 |
| 参考文献 | 第54-58页 |
| 致谢 | 第58-59页 |
| 攻读学位期间发表的学术论文目录 | 第59页 |