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

图书标准信息

• 作者 王建良
• 出版社 科学技术文献出版社
• 出版时间 2020-09
• 版次 1
• ISBN 9787518950881
• 定价 28.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸

【内容简介】

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

【目录】

第1章引言1

第2章形式语言与自动机11

21抽象代数知识准备11

22形式语言与自动机12

221字符串和语言12

222有穷状态自动机13

23图灵机形式化定义15

24下推自动机及其模型18

25分布式计算和并行计算19

26自动机理论基础21

261自动机定义22

262自动机理论22

263有限自动机理论22

264无限自动机理论23

265概率自动机理论23

266细胞自动机理论23

267抽象自动机理论24

27自动机理论与其他学科的关系24

271与数学学科的关系24

272与形式语言的关系24

273与控制论的关系24

274与生物领域的关系25

28交替式下推自动机与网格25

281网格计算兴起25

282网格定义26

283网格信息处理原理27

284交替式下推自动机与网格计算27

29自动机理论与先进计算28

291并行计算28

292分布式计算29

293集群计算29

294网格计算30

295云计算31

210本章小结33

第3章交替式下推自动机34

312方向交替式下推自动机的定义与性质34

32强loglog n空间限定的2DPDA识别性证明37

33本章小结40

第4章多墨水点交替式下推自动机的计算复杂性研究41

41定义和标识约定41

42多墨水点交替式下推自动机的墨水点层次性42

43全称状态与存在状态计算方式的不可比较性46

44本章小结51

第5章多墨水点交替式下推自动机的闭包属性53

51多墨水点非确定性下推自动机的闭包属性53

52仅有全称状态的多墨水点交替式下推自动机的闭包属性56

53本章小结61

第6章交替式下推自动机语言运算的封闭性62

61格局相关的有穷控制器的状态62

62连接、星号和保持长度的同态等的运算封闭性63

632方向交替式下推自动机闭包属性的结果69

第7章自验证的1墨水点非确定性下推自动机70

71自验证的1墨水点非确定性下推自动机的概念70

72有无墨水点的非确定性下推自动机之间的关系71

73本章小结74

第８章亚对数空间限定的多墨水点交替式下推自动机的闭包属性75

81具有k个墨水点的图灵机75

82多墨水点交替式下推自动机的闭包属性76

83语言族m2UPDAk(L(n))运算的不封闭性79

第9章总结和展望81

91研究总结81

92研究展望82

参考文献84

附录符号及术语表90