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

论文摘要

本文中，我们对理论计算机科学中的下界问题及其意义进行了简要的综述，并阐述了作者在ω-自动机转换的状态复杂性和形式语言中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（英文摘要）
• 第一章 理论计算机科学中下界问题的简要综述
• 1.1 下界问题及其意义
• 1.1.1 翻煎饼问题
• 1.1.2 抽象的数学描述
• 1.1.3 复杂性度量
• 1.1.4 上界问题
• 1.1.5 下界问题及其意义
• 1.2 一些典型的下界问题领域
• 1.2.1 自动机转换的状态复杂性
• 1.2.2 形式语言中的下界问题
• 1.2.3 电路复杂性
• 1.2.4 算法的下界分析
• 1.2.5 小结
• 第二章 ω-自动机求补操作的下界研究
• 2.1 简介
• 2.1.1 Full自动机和Sakoda-Sipser语言
• 2.2 一些基本定义
• 2.3 Full自动机技巧
• 2.4 Büchi自动机的求补操作
• 2.4.1 Kupferman-Vardi构造
• 2.4.2 下界证明
• 2.4.3 小字符集的情况
• 2.4.4 其他转换操作
• 2.5 广义Büchi自动机的求补操作:
• n,k'>2.5.1 标准广义Full Büchi自动机FB_n,k
• 2.5.2 Michel的技巧的一种推广
• n,k的一个冲突集'>2.5.3 FB_n,k的一个冲突集
• 2.5.4 下界结果
• 2.6 小结
• 第三章 基于split游戏的对正规语言分类的方法
• 3.1 简介
• 3.1.1 相关工作
• 3.2 正则表达式与正则表达式类
• 3.3 split游戏
• 3.4 split游戏应用的简单例子
• 3.5 一种到ω正则语言情形的推广
• 3.6 Omega Power问题
• 3.6.1 问题的引入
• 3.6.2 证明
• 3.6.2.1 规范的ω-分割
• 3.6.2.2 Jumping自动机
• 3.6.2.3 赢取（ω,n）-游戏
• 结论
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录