理論計(jì)算機(jī)科學(xué)中的若干下界結(jié)果.pdf

1、本文對(duì)理論計(jì)算機(jī)科學(xué)中的下界問題及其意義進(jìn)行了簡要的綜述，并闡述了作者在ω-自動(dòng)機(jī)換的狀態(tài)復(fù)雜性和形式語言中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ī)的操作上。具體地，證明了一個(gè)Buchi自動(dòng)機(jī)求補(bǔ)的Ω（(0.76n)n）的下界，并且證明了這個(gè)下界對(duì)于幾乎所有ω-自動(dòng)機(jī)的求補(bǔ)和確定化操作都有效。也證明

2、了一個(gè)廣義Buchi自動(dòng)機(jī)求補(bǔ)的Ω（(nk)）n的下界，而這個(gè)下界對(duì)于Streett自動(dòng)機(jī)的求補(bǔ)也有效。該項(xiàng)工作發(fā)表在了歐洲頂級(jí)的ICALP理論會(huì)議上，并獲得最佳學(xué)生論文獎(jiǎng)。 關(guān)于star height問題，引入了split游戲，一種邏輯中EhrenfeuchtFraisse游戲的變種，并證明了這種游戲能用于分析廣義正則表達(dá)式的表達(dá)能力。也把split游戲推廣到了廣義ω-正則表達(dá)式。為了理解這種游戲如何能被用來攻克著名的困難的s