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

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

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

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

【文章目錄】：
摘要
ABSTRACT（英文摘要）
第一章 理論計(jì)算機(jī)科學(xué)中下界問題的簡(jiǎn)要綜述
    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 自動(dòng)機(jī)轉(zhuǎn)換的狀態(tài)復(fù)雜性
        1.2.2 形式語(yǔ)言中的下界問題
        1.2.3 電路復(fù)雜性
        1.2.4 算法的下界分析
        1.2.5 小結(jié)
第二章 ω-自動(dòng)機(jī)求補(bǔ)操作的下界研究
    2.1 簡(jiǎn)介
        2.1.1 Full自動(dòng)機(jī)和Sakoda-Sipser語(yǔ)言
    2.2 一些基本定義
    2.3 Full自動(dòng)機(jī)技巧
    2.4 Büchi自動(dòng)機(jī)的求補(bǔ)操作
        2.4.1 Kupferman-Vardi構(gòu)造
        2.4.2 下界證明
        2.4.3 小字符集的情況
        2.4.4 其他轉(zhuǎn)換操作
    2.5 廣義Büchi自動(dòng)機(jī)的求補(bǔ)操作:
n,k">        2.5.1 標(biāo)準(zhǔn)廣義Full Büchi自動(dòng)機(jī)FBn,k

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



本文編號(hào)：2935827

suoshi