亞對數空間限定多墨水點交替式下推自動機的計算復雜性 內容簡介

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