多墨水点两方向交替式下推自动机的研究
本论文引入了多墨水点两方向交替式下推自动机，它是一个具有额外能力的两方向交替式下推自动机，能够用K个墨水点在输入带上标记出最多K个单元格。Chandra、Kozen和Stockmeyer引入了交替性作为并行计算的一个理论模型。交替式(alternating)图灵机是非确定性图灵机的推广，它的状态集合被分为万能状态(universal state)和存在状态(existential state)。
近年来，对具有较小空间复杂性的交替式图灵机的研究取得了很大进展，得出了许多可喜的成果。研究具有亚对数空间复杂度的交替式下推自动机的性质是非常有意义的，因为我们认为它们可以作为一种有用的且比交替式图灵机更简单的并行计算模型来研究。然而，就我们所知，对具有较小空间复杂度的交替式下推自动机(特别是具有亚对数空间复杂度的)的研究还很少。本论文主要对墨水点的个数对亚对数空间限定且仅有万能状态的多墨水点两方向交替式下推自动机的语言受理能力的影响，以及亚对数空间限定且仅有存在(万能)状态的1墨水点两方向交替式下推自动机的闭包属性进行研究。本论文分别从以下七个章节进行论述。
第一章，首先介绍了课题研究的对象和自动机的发展史以及课题实现的具体目标和意义。
第二章，主要介绍了自动机理论基础知识，其中包括自动机的定义、自动机理论的分类以及自动机和其他学科的关系，又给出了集合的几种基本运算和封闭性的概念定义，最后介绍了几种经典自动机，如图灵机、有穷自动机、下推自动机等。
第三章，分析了交替式下推自动机和网格计算之间的联系。介绍了交替式下推自动机和网格计算的相似性，希望通过研究交替式下推自动机的某些性质来研究网格计算。
第四章，给出了一些必要的定义和记号。
第五、六章，是本文的创新点和重点。
第五章，主要研究了墨水点的个数对亚对数空间限定且仅有万能状态的多墨水点两方向交替式下推自动机的语言受理能力的影响。
第六章，首先介绍了目前国内外交替式下推自动机的研究现状，其中包括1)交替式下推自动机的闭包属性；2)有无l墨水点亚对数空间限定交替式下推自动机之间的关系，最后重点证明了交替式下推自动机的闭包属性。主要证明了对任意的函数L(n)≥log log n且(n)=o(10gn)，具有一个墨水点的弱(强)L(n)空间限定且仅有存在状态(或万能状态)的交替式下推自动机所接受语言的集合对以下操作是不封闭的，如与正则语言的连接，保持长度的同态及Kleene闭包。
第七章作为结束语，对论文所作的工作进行了总结，并对下一步的工作进行了展望。
交替式下推自动机;多墨水点;亚对数空间限定;闭包属性;计算复杂性;图灵机;网格计算
中国海洋大学
硕士
计算机应用技术
徐建良
2006
中文
TP23;TP301.1
50
2007-08-07（万方平台首次上网日期，不代表论文的发表时间）