本论文引入了多墨水点两方向交替式下推自动机,它是一个具有额外能力的两方向交替式下推自动机,能够用k个墨水点在输入带上标记出最多k个单元格。Chandra、Kozen和Stockmeyer引入了交替性作为并行计算的一个理论模型。交替式(alternating)图灵机是非确定性图灵机的推广,它的状态集合被分为万能状态(universal state)和存在状态(existential state)。近年来,对具有较小空间复杂性的交替式图灵机的研究取得了很大进展,得出了许多可喜的成果。研究具有亚对数空间复杂度的交替式下推自动机的性质是非常有意义的,因为我们认为它们可以作为一种有用的且比交替式图灵机更简单的并行计算模型来研究。然而,就我们所知,对具有较小空间复杂度的交替式下推自动机(特别是具有亚对数空间复杂度的)的研究还很少。本论文主要对墨水点的个数对亚对数空间限定且仅有万能状态的多墨水点两方向交替式下推自动机的语言受理能力的影响,以及亚对数空间限定且仅有存在(万能)状态的1墨水点两方向交替式下推自动机的闭包属性进行研究。本论文分别从以下七个章节进行论述。第一章,首先介绍了课题研究的对象和自动机的发展史以及课题实现的具体目标和意义。第二章,主要介绍了自动机理论基础知识,其中包括自动机的定义、自动机理论的分类以及自动机和其他学科的关系,又给出了集合的几种基本运算和封闭性的概念定义,最后介绍了几种经典自动机,如图灵机、有穷自动机、下推自动机等。第三章,分析了交替式下推自动机和网格计算之间的联系。介绍了交替式下推自动机和网格计算的相似性,希望通过研究交替式下推自动机的某些性质来研究网格计算。第四章,给出了一些必要的定义和记号。第五、六章,是本文的创新点和重点。第五章,主要研究了墨水点的个数对亚对数空间限定且仅有万能状态的多墨水点两方向交替式下推自动机的语言受理能力的影响。