本书引入两种类型的机器模型，即具有亚对数空间的2方向交替式下推自动机和具有多个墨水点的交替式下推自动机，并对这两种类型自动机模型的一些重要性质进行了深入研究，并提出了多墨水点交替式下推自动机的概念；研究了在亚对数空间下，墨水点个数对仅有全称状态的多墨水点交替式下推自动机计算能力的影响；证明了亚对数空间限定的仅有全称状态的多墨水点交替式下推自动机计算能力随着墨水点个数的增加而增强，研究了在亚对数空间下，仅有全称状态和仅有存在状态的多墨水点交替式下推自动机计算能力的关系，证明了它们的计算能力是不可比较的；论证了在亚对数空间下，仅有全称状态的多墨水点交替式下推自动机所识别的语言族，以及仅有存在状态的多墨水点交替式下推自动机所识别语言族的闭包属性，证明了这些语言族在补、与正则语言的连接、星号及保持长度的同态运算下是不封闭的；引入自验证的1墨水点2方向非确定性下推自动机，证明了在亚对数空间下。具有1墨水点的非确定性下推自动机计算能力比具有1墨水点的自验证非确定性下推自动机的计算能力强。本书最后讨论了相关的几个尚待研究解决的问题，提出了今后研究的方向。

第1章 引言
第2章 形式语言与自动机
2.1 抽象代数知识准备
2.2 形式语言与自动机
2.2.1 字符串和语言
2.2.2 有穷状态自动机
2.3 图灵机形式化定义
2.4 下推自动机及其模型
2.5 分布式计算和并行计算
2.6 自动机理论基础
2.6.1 自动机定义
2.6.2 自动机理论
2.6.3 有限自动机理论
2.6.4 无限自动机理论
2.6.5 概率自动机理论
2.6.6 细胞自动机理论
2.6.7 抽象自动机理论
2.7 自动机理论与其他学科的关系
2.7.1 与数学学科的关系
2.7.2 与形式语言的关系
2.7.3 与控制论的关系
2.7.4 与生物领域的关系
2.8 交替式下推自动机与网格
2.8.1 网格计算兴起
2.8.2 网格定义
2.8.3 网格信息处理原理
2.8.4 交替式下推自动机与网格计算
2.9 自动机理论与先进计算
2.9.1 并行计算
2.9.2 分布式计算
2.9.3 集群计算
2.9.4 网格计算
2.9.5 云计算
2.10 本章小结
第3章 交替式下推自动机
3.1 2方向交替式下推自动机的定义与性质
3.2 强loglog n空间限定的2DPDA识别性证明
3.3 本章小结
第4章 多墨水点交替式下推自动机的计算复杂性研究
4.1 定义和标识约定
4.2 多墨水点交替式下推自动机的墨水点层次性
4.3 全称状态与存在状态计算方式的不可比较性
4.4 本章小结
第5章 多墨水点交替式下推自动机的闭包属性
5.1 多墨水点非确定性下推自动机的闭包属性
5.2 仅有全称状态的多墨水点交替式下推自动机的闭包属性
5.3 本章小结
第6章 交替式下推自动机语言运算的封闭性
6.1 格局相关的有穷控制器的状态
6.2 连接、星号和保持长度的同态等的运算封闭性
6.3 2方向交替式下推自动机闭包属性的结果
第7章 自验证的1墨水点非确定性下推自动机
7.1 自验证的1墨水点非确定性下推自动机的概念
7.2 有无墨水点的非确定性下推自动机之间的关系
7.3 本章小结
第8章 亚对数空间限定的多墨水点交替式下推自动机的闭包属性
8.1 具有k个墨水点的图灵机
8.2 多墨水点交替式下推自动机的闭包属性
8.3 语言族m-2UPDAk (L(n)) 运算的不封闭性
第9章 总结和展望
9.1 研究总结
9.2 研究展望
参考文献
附录 符号及术语表