本文中，我們對理論計算機科學(xué)中的下界問題及其意義進行了簡要的綜述，并闡述了作者在ω-自動機轉(zhuǎn)換的狀態(tài)復(fù)雜性和形式語言中starheight問題上的兩項研究工作。 在ω-自動機轉(zhuǎn)換上，我們首先提出了一種證明自動機狀態(tài)轉(zhuǎn)換復(fù)雜性下界的技巧，即full自動機技巧，然后將這種技巧應(yīng)用到非確定ω-自動機的求補操作上。具體地，我們證明了一個Buchi自動機求補的Ω（（0.76n）ⁿ）的下界，并且證明了這個下界對于幾乎所有ω-自動機的求補和確定化操作都有效。我們也證明了一個廣義Buchi自動機求補的（Ω（nk））ⁿ的下界，而這個下界對于Streett自動機的求補也有效。該項工作發(fā)表在了歐洲頂級的ICALP理論會議上，并獲得最佳學(xué)生論文獎。 關(guān)于star height問題，我們引入了split游戲，一種邏輯中Ehrenfeucht-Fra（?）ssé游戲的變種，并證明了這種游戲能用于分析廣義正則表達式的表達能力。我們也把split游戲推廣到了廣義ω-正則表達式。為了理解這種游戲如何能被用來攻克著名的困難的star height 2問題，我們提出并... 

【文章來源】：上海交通大學(xué)上海市 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：59 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
ABSTRACT（英文摘要）
第一章 理論計算機科學(xué)中下界問題的簡要綜述
    1.1 下界問題及其意義
        1.1.1 翻煎餅問題
        1.1.2 抽象的數(shù)學(xué)描述
        1.1.3 復(fù)雜性度量
        1.1.4 上界問題
        1.1.5 下界問題及其意義
    1.2 一些典型的下界問題領(lǐng)域
        1.2.1 自動機轉(zhuǎn)換的狀態(tài)復(fù)雜性
        1.2.2 形式語言中的下界問題
        1.2.3 電路復(fù)雜性
        1.2.4 算法的下界分析
        1.2.5 小結(jié)
第二章 ω-自動機求補操作的下界研究
    2.1 簡介
        2.1.1 Full自動機和Sakoda-Sipser語言
    2.2 一些基本定義
    2.3 Full自動機技巧
    2.4 Büchi自動機的求補操作
        2.4.1 Kupferman-Vardi構(gòu)造
        2.4.2 下界證明
        2.4.3 小字符集的情況
        2.4.4 其他轉(zhuǎn)換操作
    2.5 廣義Büchi自動機的求補操作:
n,k">        2.5.1 標(biāo)準(zhǔn)廣義Full Büchi自動機FBn,k

        2.5.2 Michel的技巧的一種推廣
n,k的一個沖突集">        2.5.3 FB_n,k的一個沖突集
        2.5.4 下界結(jié)果
    2.6 小結(jié)
第三章 基于split游戲的對正規(guī)語言分類的方法
    3.1 簡介
        3.1.1 相關(guān)工作
    3.2 正則表達式與正則表達式類
    3.3 split游戲
    3.4 split游戲應(yīng)用的簡單例子
    3.5 一種到ω正則語言情形的推廣
    3.6 Omega Power問題
        3.6.1 問題的引入
        3.6.2 證明
            3.6.2.1 規(guī)范的ω-分割
            3.6.2.2 Jumping自動機
            3.6.2.3 贏�。é�,n）-游戲
結(jié)論
參考文獻
致謝
攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄



本文編號：2935827

suoshi