亞對數(shù)空間限定多墨水點(diǎn)交替式下推自動機(jī)的計(jì)算復(fù)雜性

　　交替式下推自動機(jī)是當(dāng)前并行與分布式計(jì)算環(huán)境的數(shù)學(xué)模型，而墨水點(diǎn)是對移動智能體在宿主機(jī)器上寫入信息的一種模擬，交替式下推自動機(jī)的研究對于解明基于互聯(lián)網(wǎng)的并行與分布式計(jì)算的復(fù)雜性具有重要的理論意義。 交替式是由Chandra、Kozen和Stockmeyer提出來的一個并行與分布式計(jì)算的理論模型。交替式圖靈機(jī)（Alternating Turing Machine）是對非確定性圖靈機(jī)的一個擴(kuò)展，它的有窮狀態(tài)被分為全稱狀態(tài)（Universal State）和存在狀態(tài)（Existential State）兩種不同的計(jì)算狀態(tài)。交替式圖靈機(jī)采用交替的方式，不斷采用存在和全稱兩種計(jì)算方式進(jìn)行計(jì)算，已經(jīng)證明，這種交替式計(jì)算模式有效地提高了計(jì)算能力，交替式下推自動機(jī)則是比交替式圖靈機(jī)更為簡單的計(jì)算模型。關(guān)于亞對數(shù)空間限定的交替式圖靈機(jī)的研究取得了較大進(jìn)展，但是，目前國際上關(guān)于多墨水點(diǎn)交替式下推自動機(jī)的研究還比較少。 本書引入兩種類型的機(jī)器模型，即具有亞對數(shù)空間的2方向交替式下推自動機(jī)和具有多個墨水點(diǎn)的交替式下推自動機(jī)，并對這兩種類型自動機(jī)模型的一些重要性質(zhì)進(jìn)行了深入研究，并提出了多墨水點(diǎn)交替式下推自動機(jī)的概念；研究了在亞對數(shù)空間下，墨水點(diǎn)個數(shù)對僅有全稱狀態(tài)的多墨水點(diǎn)交替式下推自動機(jī)計(jì)算能力的影響；證明了亞對數(shù)空間限定的僅有全稱狀態(tài)的多墨水點(diǎn)交替式下推自動機(jī)計(jì)算能力隨著墨水點(diǎn)個數(shù)的增加而增強(qiáng)，研究了在亞對數(shù)空間下，僅有全稱狀態(tài)和僅有存在狀態(tài)的多墨水點(diǎn)交替式下推自動機(jī)計(jì)算能力的關(guān)系，證明了它們的計(jì)算能力是不可比較的；論證了在亞對數(shù)空間下，僅有全稱狀態(tài)的多墨水點(diǎn)交替式下推自動機(jī)所識別的語言族，以及僅有存在狀態(tài)的多墨水點(diǎn)交替式下推自動機(jī)所識別語言族的閉包屬性，證明了這些語言族在補(bǔ)、與正則語言的連接、星號及保持長度的同態(tài)運(yùn)算下是不封閉的；引入自驗(yàn)證的1墨水點(diǎn)2方向非確定性下推自動機(jī)，證明了在亞對數(shù)空間下，具有1墨水點(diǎn)的非確定性下推自動機(jī)計(jì)算能力比具有1墨水點(diǎn)的自驗(yàn)證非確定性下推自動機(jī)的計(jì)算能力強(qiáng)。本書最后討論了相關(guān)的幾個尚待研究解決的問題，提出了今后研究的方向。

暫缺《亞對數(shù)空間限定多墨水點(diǎn)交替式下推自動機(jī)的計(jì)算復(fù)雜性》作者簡介