多墨水點(diǎn)兩方向交替式下推自動(dòng)機(jī)的研究.pdf

1、本論文引入了多墨水點(diǎn)兩方向交替式下推自動(dòng)機(jī)，它是一個(gè)具有額外能力的兩方向交替式下推自動(dòng)機(jī)，能夠用K個(gè)墨水點(diǎn)在輸入帶上標(biāo)記出最多K個(gè)單元格。Chandra、Kozen和Stockmeyer引入了交替性作為并行計(jì)算的一個(gè)理論模型。交替式(alternating)圖靈機(jī)是非確定性圖靈機(jī)的推廣，它的狀態(tài)集合被分為萬(wàn)能狀態(tài)(universal state)和存在狀態(tài)(existential state)。 近年來(lái)，對(duì)具有較小空間復(fù)雜性的

2、交替式圖靈機(jī)的研究取得了很大進(jìn)展，得出了許多可喜的成果。研究具有亞對(duì)數(shù)空間復(fù)雜度的交替式下推自動(dòng)機(jī)的性質(zhì)是非常有意義的，因?yàn)槲覀冋J(rèn)為它們可以作為一種有用的且比交替式圖靈機(jī)更簡(jiǎn)單的并行計(jì)算模型來(lái)研究。然而，就我們所知，對(duì)具有較小空間復(fù)雜度的交替式下推自動(dòng)機(jī)(特別是具有亞對(duì)數(shù)空間復(fù)雜度的)的研究還很少。本論文主要對(duì)墨水點(diǎn)的個(gè)數(shù)對(duì)亞對(duì)數(shù)空間限定且僅有萬(wàn)能狀態(tài)的多墨水點(diǎn)兩方向交替式下推自動(dòng)機(jī)的語(yǔ)言受理能力的影響，以及亞對(duì)數(shù)空間限定且僅有存在(萬(wàn)

3、能)狀態(tài)的1墨水點(diǎn)兩方向交替式下推自動(dòng)機(jī)的閉包屬性進(jìn)行研究。本論文分別從以下七個(gè)章節(jié)進(jìn)行論述。 第一章，首先介紹了課題研究的對(duì)象和自動(dòng)機(jī)的發(fā)展史以及課題實(shí)現(xiàn)的具體目標(biāo)和意義。 第二章，主要介紹了自動(dòng)機(jī)理論基礎(chǔ)知識(shí)，其中包括自動(dòng)機(jī)的定義、自動(dòng)機(jī)理論的分類以及自動(dòng)機(jī)和其他學(xué)科的關(guān)系，又給出了集合的幾種基本運(yùn)算和封閉性的概念定義，最后介紹了幾種經(jīng)典自動(dòng)機(jī)，如圖靈機(jī)、有窮自動(dòng)機(jī)、下推自動(dòng)機(jī)等。 第三章，分析了交替式下推自

4、動(dòng)機(jī)和網(wǎng)格計(jì)算之間的聯(lián)系。介紹了交替式下推自動(dòng)機(jī)和網(wǎng)格計(jì)算的相似性，希望通過(guò)研究交替式下推自動(dòng)機(jī)的某些性質(zhì)來(lái)研究網(wǎng)格計(jì)算。 第四章，給出了一些必要的定義和記號(hào)。 第五、六章，是本文的創(chuàng)新點(diǎn)和重點(diǎn)。 第五章，主要研究了墨水點(diǎn)的個(gè)數(shù)對(duì)亞對(duì)數(shù)空間限定且僅有萬(wàn)能狀態(tài)的多墨水點(diǎn)兩方向交替式下推自動(dòng)機(jī)的語(yǔ)言受理能力的影響。 第六章，首先介紹了目前國(guó)內(nèi)外交替式下推自動(dòng)機(jī)的研究現(xiàn)狀，其中包括1)交替式下推自動(dòng)機(jī)的閉包屬性

5、；2)有無(wú)l墨水點(diǎn)亞對(duì)數(shù)空間限定交替式下推自動(dòng)機(jī)之間的關(guān)系，最后重點(diǎn)證明了交替式下推自動(dòng)機(jī)的閉包屬性。主要證明了對(duì)任意的函數(shù)L(n)≥log log n且(n)=o(10gn)，具有一個(gè)墨水點(diǎn)的弱(強(qiáng))L(n)空間限定且僅有存在狀態(tài)(或萬(wàn)能狀態(tài))的交替式下推自動(dòng)機(jī)所接受語(yǔ)言的集合對(duì)以下操作是不封閉的，如與正則語(yǔ)言的連接，保持長(zhǎng)度的同態(tài)及Kleene閉包。 第七章作為結(jié)束語(yǔ)，對(duì)論文所作的工作進(jìn)行了總結(jié)，并對(duì)下一步的工作進(jìn)行了展望