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

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

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