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

发布时间：2020-12-24 14:37

　　本文中，我们对理论计算机科学中的下界问题及其意义进行了简要的综述，并阐述了作者在ω-自动机转换的状态复杂性和形式语言中starheight问题上的两项研究工作。 在ω-自动机转换上，我们首先提出了一种证明自动机状态转换复杂性下界的技巧，即full自动机技巧，然后将这种技巧应用到非确定ω-自动机的求补操作上。具体地，我们证明了一个Buchi自动机求补的Ω（（0.76n）ⁿ）的下界，并且证明了这个下界对于几乎所有ω-自动机的求补和确定化操作都有效。我们也证明了一个广义Buchi自动机求补的（Ω（nk））ⁿ的下界，而这个下界对于Streett自动机的求补也有效。该项工作发表在了欧洲顶级的ICALP理论会议上，并获得最佳学生论文奖。 关于star height问题，我们引入了split游戏，一种逻辑中Ehrenfeucht-Fra（?）ssé游戏的变种，并证明了这种游戏能用于分析广义正则表达式的表达能力。我们也把split游戏推广到了广义ω-正则表达式。为了理解这种游戏如何能被用来攻克著名的困难的star height 2问题，我们提出并... 

【文章来源】：上海交通大学上海市 211工程院校 985工程院校 教育部直属院校

【文章页数】：59 页

【学位级别】：硕士

【文章目录】：
摘要
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自动机FBn,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）-游戏
结论
参考文献
致谢
攻读学位期间发表的学术论文目录



本文编号：2935827

suoshi