本论文研究具有多个墨水点的交替式下推自动机(multi-inkdot two-way alter-nating pushdown automata, multi-indot 2APDA’s).交替性是由Chandra、Kozen和Stockmeyer提出来的,是一个并行与分布式计算的理论模型.交替式图灵机(alternating Turing machine)是对非确定性图灵机的一个扩展,它的有穷状态被分为全称状态(universal state)和存在状态(existential state)两种不同的计算状态.非确定性图灵机可看作只有存在状态的交替式图灵机.交替式自动机进入存在状态,可以在多种可能性中选择一个可行的；而进入全称状态时,就协同地对多种可能性进行并行计算,当且仅当所有可能性都可行时,整个计算才是可行的.交替式图灵机采用交替的方式,不断采用存在和全称两种计算方式进行计算.已经证明,这种交替式计算模式有效地提高了计算能力.这种交替式计算模式是对当前网络中并行和分布式计算的很好的模拟.其中,存在计算模式是对分布式计算的模拟,只要能够得到分布于互联网上的多台主机中的任意一台的计算资源即可；而全称、计算模式是对并行计算的模拟,在获取到的主机的多个CPU上并行处理,必须所有的并行计算分支都返回结果才能够得出计算结果.目前,关于亚对数空间限定的交替式图灵机的研究取得了较大的进展.交替式下推自动机作为比交替式图灵机更为简单的计算模型,对于解明并行与分布式计算的计算复杂性问题具有重要理论意义,但是,目前这方面的研究,特别是关于多墨水点交替式下推自动机的研究还比较少.基于上述原因,本论文关于亚对数空间的多墨水点交替式下推自动机的研究意义是很显然的.我们引入两种类型的机器模型,即具有亚对数空间的2APDA和具有多个墨水点的交替式下推自动机,并对这两种类型的自动机模型的一些重要性质进行深入的研究.本论文共包括8章.第一章简要介绍了形式语言、自动机和计算复杂性理论的主要研究分支和研究热点,并对国内外的研究现状进行了综述,从而从整体上论述了本论文的选题依据和研究意义.第二章在第一章的基础上,进一步给出了与本文研究内容密切相关的有穷状态自动机、自验证的自动机、图灵机和下推自动机的形式化定义.同时,也给出了有关抽象代数、形式语言的一些概念的形式化定义.第三章给出了两方向交替式下推自动机(2APDA)及其复杂性语言族的定义.同时,也给出了贯穿全文的一些记号和字符串模式.在此基础上,给出一个引理,其结论成为后面几章的定理证明的前提,该引理的证明中所给出的识别某些字符串模式的算法对后面的证明也有参考价值.在第四章中,我们首先提出多墨水点交替式下推自动机(multi-inkdot two-way alternating pushdown automaton)的概念.一个k墨水点交替式下推自动机(k-inkdot two-way alternating pushdown automaton),k≥0,是一个具有k个墨水点的2APDA,它可以使用这k个墨水点标记出输入带上的k个单元格.一旦某个墨水点被用来标记输入带上的某个单元格后,这个墨水点就不会被清除掉,从而也不能回收再利用,而且最多有k个可用的墨水点.我们首先研究在亚对数空间下,墨水点个数对仅有全称状态的多墨水点交替式下推自动机的计算能力的影响.我们证明了亚对数空间限定的仅有全称状态的多墨水点交替式下推自动机的计算能力随着墨水点个数的增加而增加,即这些机器的计算能力在墨水点个数上存在着无限的可扩展性.我们还研究了在亚对数空间下,仅有全称状态的多墨水点交替式下推自动机和仅有存在状态的多墨水点交替式下推自动机的计算能力的关系,我们证明了他们的计算能力是不可比较的,从而把文献[67]中的结果扩展到了多个墨水点的情况.在第五章中,我们研究在亚对数空间下,仅有全称状态的多墨水点交替式下推自动机所识别的语言族,和仅有存在状态的多墨水点交替式下推自动机所识别的语言族的闭包属性.我们证明了这些语言族在补、与正则语言的连结、星号、以及保持长度的同态运算下是不封闭的.本论文的这些结果是对文献[68]中的结果的一个扩展.在第六章中,我们转而研究亚对数空间限定的没有墨水点的交替式下推自动机所识别语言族的闭包属性,证明了对数空间限定的交替式下推自动机所识别语言族在连结、星号、以及保持长度的同态运算下是不封闭的,从而解决了文献[65]中所列出的未解决问题.在第七章中,我们引入自验证的1墨水点2方向非确定性下推自动机(self-verifying 1-inkdot two-way nondeterministic pushdown automaton),它是具有1个墨水点的自验证的非确定性下推自动机.我们证明了在亚对数空间下,具有1个墨水点的非确定性下推自动机的计算能力比具有1个墨水点的自验证的非确定性下推自动机的计算能力强.第八章总结论文中所得到的结论及其意义,同时还提出了今后研究工作的方向,讨论了相关的几个尚待研究解决的问题.