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

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

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

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

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

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

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

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

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

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