亞對(duì)數(shù)空間限定多墨水點(diǎn)交替式下推自動(dòng)機(jī)的研究.pdf

1、本論文研究具有多個(gè)墨水點(diǎn)的交替式下推自動(dòng)機(jī)(mtdti-inkdot two-way alternating pushdown automata,multi-indot 2APDA's).交替性是由Chandra、Kozen和Stockmeyer提出來(lái)的,是一個(gè)并行與分布式計(jì)算的理論模型.交替式圖靈機(jī)(alternating Turing machine)是對(duì)非確定性圖靈機(jī)的一個(gè)擴(kuò)展,它的有窮狀態(tài)被分為全稱(chēng)狀態(tài)(universal st

2、ate)和存在狀態(tài)(existential state)兩種不同的計(jì)算狀態(tài).非確定性圖靈機(jī)可看作只有存在狀態(tài)的交替式圖靈機(jī).交替式自動(dòng)機(jī)進(jìn)入存在狀態(tài),可以在多種可能性中選擇一個(gè)可行的;而進(jìn)入全稱(chēng)狀態(tài)時(shí),就協(xié)同地對(duì)多種可能性進(jìn)行并行計(jì)算,當(dāng)且僅當(dāng)所有可能性都可行時(shí),整個(gè)計(jì)算才是可行的.交替式圖靈機(jī)采用交替的方式,不斷采用存在和全稱(chēng)兩種計(jì)算方式進(jìn)行計(jì)算.已經(jīng)證明,這種交替式計(jì)算模式有效地提高了計(jì)算能力.這種交替式計(jì)算模式是對(duì)當(dāng)前網(wǎng)絡(luò)中并行和

3、分布式計(jì)算的很好的模擬.其中,存在計(jì)算模式是對(duì)分布式計(jì)算的模擬,只要能夠得到分布于互聯(lián)網(wǎng)上的多臺(tái)主機(jī)中的任意一臺(tái)的計(jì)算資源即可;而全稱(chēng)計(jì)算模式是對(duì)并行計(jì)算的模擬,在獲取到的主機(jī)的多個(gè)CPU上并行處理,必須所有的并行計(jì)算分支都返回結(jié)果才能夠得出計(jì)算結(jié)果.目前,關(guān)于亞對(duì)數(shù)空間限定的交替式圖靈機(jī)的研究取得了較大的進(jìn)展.
　　 交替式下推自動(dòng)機(jī)作為比交替式圖靈機(jī)更為簡(jiǎn)單的計(jì)算模型,對(duì)于解明并行與分布式計(jì)算的計(jì)算復(fù)雜性問(wèn)題具有重要理論意義

4、,但是,目前這方面的研究,特別是關(guān)于多墨水點(diǎn)交替式下推自動(dòng)機(jī)的研究還比較少.基于上述原因,本論文關(guān)于亞對(duì)數(shù)空間的多墨水點(diǎn)交替式下推自動(dòng)機(jī)的研究意義是很顯然的.我們引入兩種類(lèi)型的機(jī)器模型,即具有亞對(duì)數(shù)空間的2APDA和具有多個(gè)墨水點(diǎn)的交替式下推自動(dòng)機(jī),并對(duì)這兩種類(lèi)型的自動(dòng)機(jī)模型的一些重要性質(zhì)進(jìn)行深入的研究.本論文共包括8章.
　　 第一章簡(jiǎn)要介紹了形式語(yǔ)言、自動(dòng)機(jī)和計(jì)算復(fù)雜性理論的主要研究分支和研究熱點(diǎn),并對(duì)國(guó)內(nèi)外的研究現(xiàn)狀進(jìn)行了

5、綜述,從而從整體上論述了本論文的選題依據(jù)和研究意義.
　　 第二章在第一章的基礎(chǔ)上,進(jìn)一步給出了與本文研究?jī)?nèi)容密切相關(guān)的有窮狀態(tài)自動(dòng)機(jī)、自驗(yàn)證的自動(dòng)機(jī)、圖靈機(jī)和下推自動(dòng)機(jī)的形式化定義.同時(shí),也給出了有關(guān)抽象代數(shù)、形式語(yǔ)言的一些概念的形式化定義.
　　 第三章給出了兩方向交替式下推自動(dòng)機(jī)(2APDA)及其復(fù)雜性語(yǔ)言族的定義.同時(shí),也給出了貫穿全文的一些記號(hào)和字符串模式.在此基礎(chǔ)上,給出一個(gè)引理,其結(jié)論成為后面幾章的定理證明

6、的前提,該引理的證明中所給出的識(shí)別某些字符串模式的算法對(duì)后面的證明也有參考價(jià)值.
　　 在第四章中,我們首先提出多墨水點(diǎn)交替式下推自動(dòng)機(jī)(multi-inkdot two-way alternating pushdown automaton)的概念.一個(gè)k墨水點(diǎn)交替式下推自動(dòng)機(jī)(k-inkdot two-way alternating pushdown automaton),k≥0,是一個(gè)具有k個(gè)墨水點(diǎn)的2APDA,它可以使用這

7、k個(gè)墨水點(diǎn)標(biāo)記出輸入帶上的k個(gè)單元格.一旦某個(gè)墨水點(diǎn)被用來(lái)標(biāo)記輸入帶上的某個(gè)單元格后,這個(gè)墨水點(diǎn)就不會(huì)被清除掉,從而也不能回收再利用,而且最多有k個(gè)可用的墨水點(diǎn).我們首先研究在亞對(duì)數(shù)空間下,墨水點(diǎn)個(gè)數(shù)對(duì)僅有全稱(chēng)狀態(tài)的多墨水點(diǎn)交替式下推自動(dòng)機(jī)的計(jì)算能力的影響.我們證明了亞對(duì)數(shù)空間限定的僅有全稱(chēng)狀態(tài)的多墨水點(diǎn)交替式下推自動(dòng)機(jī)的計(jì)算能力隨著墨水點(diǎn)個(gè)數(shù)的增加而增加,即這些機(jī)器的計(jì)算能力在墨水點(diǎn)個(gè)數(shù)上存在著無(wú)限的可擴(kuò)展性.我們還研究了在亞對(duì)數(shù)空間

8、下,僅有全稱(chēng)狀態(tài)的多墨水點(diǎn)交替式下推自動(dòng)機(jī)和僅有存在狀態(tài)的多墨水點(diǎn)交替式下推自動(dòng)機(jī)的計(jì)算能力的關(guān)系,我們證明了他們的計(jì)算能力是不可比較的,從而把文獻(xiàn)[67]中的結(jié)果擴(kuò)展到了多個(gè)墨水點(diǎn)的情況.
　　 在第五章中,我們研究在亞對(duì)數(shù)空間下,僅有全稱(chēng)狀態(tài)的多墨水點(diǎn)交替式下推自動(dòng)機(jī)所識(shí)別的語(yǔ)言族,和僅有存在狀態(tài)的多墨水點(diǎn)交替式下推自動(dòng)機(jī)所識(shí)別的語(yǔ)言族的閉包屬性.我們證明了這些語(yǔ)言族在補(bǔ)、與正則語(yǔ)言的連結(jié)、星號(hào)、以及保持長(zhǎng)度的同態(tài)運(yùn)算下是不

9、封閉的.本論文的這些結(jié)果是對(duì)文獻(xiàn)[68]中的結(jié)果的一個(gè)擴(kuò)展.
　　 在第六章中,我們轉(zhuǎn)而研究亞對(duì)數(shù)空間限定的沒(méi)有墨水點(diǎn)的交替式下推自動(dòng)機(jī)所識(shí)別語(yǔ)言族的閉包屬性,證明了對(duì)數(shù)空間限定的交替式下推自動(dòng)機(jī)所識(shí)別語(yǔ)言族在連結(jié)、星號(hào)、以及保持長(zhǎng)度的同態(tài)運(yùn)算下是不封閉的,從而解決了文獻(xiàn)[65]中所列出的未解決問(wèn)題.
　　 在第七章中,我們引入自驗(yàn)證的1墨水點(diǎn)2方向非確定性下推自動(dòng)機(jī)(self-verifying 1-inkdot tw