摘要: 在计算机科学领域，自动机理论和形式语言理论对于理解计算和信息处理的概念与机制具有非常重要的作用。因为它们为计算机科学理论的研究提供了一个基本的思想和数学模型。所以，这些理论的研究形成了计算机科学领域的一个非常重要而有研究意义的学术分支。为了回答计算机科学领域的一个基本问题—“计算机能够解决哪些问题？”，Alan Turing提出了有名的图灵机。此后，图灵机就成为计算机的一个简练的数学模型。尽管图灵机的定义很简单，但是它有效地描述了通用计算机的计算能力。同时，为了描述计算机完成给定任务的复杂程度，计算机科学理论研究者们提出了计算复杂性的概念。时间和空间（存贮容量）是衡量计算复杂性的两个最重要的尺度。计算复杂性理论的一个重要概念是复杂性语言族（complexity class），它包括在给定的资源（时间或空间）下能够被识别的所有语言。计算机科学领域的许多难解而重要的问题就是有关不同资源下的复杂性语言族之间的包含关系的。Chandra、Kozen和Stockmeyer提出了交替性（alternation）作为并行计算的一个理论模型。交替式（alternating）图灵机是非确定性图灵机的推广，它的状态集合被分为万能状态（universal state）和存在状态（existential state）。非确定性图灵机可看作只有存在状态的交替式图灵机。近年来，对具有较小空间复杂性的交替式图灵机的研究取得了很大进展，得出了许多可喜的成果。具有较小空间复杂性的交替式下推自动机的研究是非常有意义的，因为我们认为交替式下推自动机是一个比交替式图灵机更简单的并行计算模型。交替式下推自动机进入存在状态，可以在多种可能性中选择一个可行的；而进入万能状态时，就协同地对多种可能性进行并行计算，当且仅当所有可能性都可行时，整个计算才是可行的。这种交替式计算模式是对当前网络中并行和分布式计算的很好的模拟。但是，就我们所知，对于具有较小空间复杂性的交替式下推自动机的研究还很少。为了严格地分开确定性语言族和非确定性语言族，Ranjan等提出了一个稍加修改的图灵机模型，称为1墨水点（1 inkdot）图灵机。1墨水点图灵机是一个两方向图灵机，它能够用墨水点标志出输入带上的一个单元格。对于1墨水点图灵机，确定性语言族和非确定性语言族是不相等的。本论文研究亚对数空间限定的1墨水点交替式下推自动机的闭包属性。闭包属性在计算机理论科学中应用很广。例如，关系在关系代数运算下的结果仍为关系，我们称关系集合在关系代数运算下封闭。这为关系数据库的发展提供了理论基础。因此，研究语言族的闭包属性是非常有意义的。本论文证明了（1）亚对数空间限定且仅有万能状态的1墨水点交替式下推自动机所识别的语言族在并、与正则语言的连接、保持长度的同态以及Kleene闭包等运算下是不封闭的；（2）亚对数空间限定且仅有存在状态的1墨水点交替式下推自动机所识别的语言族在交、与正则语言的连接、保持长度的同态以及Kleene闭包等运算下是不封闭的。