亚对数空间限定多墨水点交替式下推自动机的计算复杂性

内容简介

交替式下推自动机是当前并行与分布式计算环境的数学模型，而墨水点是对移动智能体在宿主机器上写入信息的一种模拟，交替式下推自动机的研究对于解明基于互联网的并行与分布式计算的复杂性具有重要的理论意义。 交替式是由Chandra、Kozen和Stockmeyer提出来的一个并行与分布式计算的理论模型。交替式图灵机（Alternating Turing Machine）是对非确定性图灵机的一个扩展，它的有穷状态被分为全称状态（Universal State）和存在状态（Existential State）两种不同的计算状态。交替式图灵机采用交替的方式，不断采用存在和全称两种计算方式进行计算，已经证明，这种交替式计算模式有效地提高了计算能力，交替式下推自动机则是比交替式图灵机更为简单的计算模型。关于亚对数空间限定的交替式图灵机的研究取得了较大进展，但是，目前国际上关于多墨水点交替式下推自动机的研究还比较少。 本书引入两种类型的机器模型，即具有亚对数空间的2方向交替式下推自动机和具有多个墨水点的交替式下推自动机，并对这两种类型自动机模型的一些重要性质进行了深入研究，并提出了多墨水点交替式下推自动机的概念；研究了在亚对数空间下，墨水点个数对仅有全称状态的多墨水点交替式下推自动机计算能力的影响；证明了亚对数空间限定的仅有全称状态的多墨水点交替式下推自动机计算能力随着墨水点个数的增加而增强，研究了在亚对数空间下，仅有全称状态和仅有存在状态的多墨水点交替式下推自动机计算能力的关系，证明了它们的计算能力是不可比较的；论证了在亚对数空间下，仅有全称状态的多墨水点交替式下推自动机所识别的语言族，以及仅有存在状态的多墨水点交替式下推自动机所识别语言族的闭包属性，证明了这些语言族在补、与正则语言的连接、星号及保持长度的同态运算下是不封闭的；引入自验证的1墨水点2方向非确定性下推自动机，证明了在亚对数空间下，具有1墨水点的非确定性下推自动机计算能力比具有1墨水点的自验证非确定性下推自动机的计算能力强。本书*后讨论了相关的几个尚待研究解决的问题，提出了今后研究的方向。