本書對亞對數空間限定多墨水點交替式下推自動機的計算復雜性問題進行了研究，主要研究工作包括：證明了亞對數空間限定的僅有全稱狀態的多墨水點交替式下推自動機的計算能力隨著墨水點個數的增加而增強；研究了在亞對數空間下，僅有全稱狀態的和僅有存在狀態的多墨水點交替式下推自動機所識別的語言族的閉包屬性；研究了自驗證的非確定性下推自動機隨機計算模型與普通的非確定性計算模型的關繫。

●  第1章引言1
●
●第2章形式語言與自動機11
●
●21抽像代數知識準備11
●
●22形式語言與自動機12
●
●221字符串和語言12
●
●222有窮狀態自動機13
●
●23圖靈機形式化定義15
●
●24下推自動機及其模型18
●
●25分布式計算和並行計算19
●
●26自動機理論基礎21
●
●部分目錄

  交替式下推自動機是當前並行與分布式計算環境的數學模型，而墨水點是對移動智能體在宿主機器上寫入信息的一種模擬，交替式下推自動機的研究對於解明基於互聯網的並行與分布式計算的復雜性具有重要的理論意義。

交替式是由Chandra、Kozen和Stockmeyer提出來的一個並行與分布式計算的理論模型。交替式圖靈機（Alternating Turing Machine）是對非確定性圖靈機的一個擴展，它的有窮狀態被分為全稱狀態（Universal State）和存在狀態（Existential State）兩種不同的計算狀態。交替式圖靈機采用交替的方式，不斷采用存在和全稱兩種計算方式進行計算，已經證明，這種交替式計算模式有效地提高了計算能力，交替式下推自動機則是比交替式圖靈機更為簡單的計算模型。關於亞對數空間限定的交替式圖靈機的研究取得了較大進展，等