若干初等元胞自动机演化语言复杂性

论文摘要

元胞自动机是研究复杂系统的一种理想化的数学模型。它可以看成一类无穷维动力系统,其特点是空间、时间和状态都离散,可用来模拟许多物理、生物和化学等复杂的自然现象。本文以形式语言和符号动力学理论为基础,运用禁止字和有限自动机等工具,研究了51个初等元胞自动机宽度为2的演化语言复杂性。在对这51个初等元胞自动机的禁止字分析之后,按照演化语言的复杂程度将这些初等元胞自动机分为三类：演化语言无禁止字；演化语言为有限补语言；演化语言为无限补正规语言。第一类初等元胞自动机的演化语言没有禁止字,自然是正规语言。第二类初等元胞自动机的演化语言只有有限个禁止字,其宽度为2的演化语言是正规语言。第三类初等元胞自动机的演化语言有无限多个禁止字,但这些禁止字存在着规律性,通过理论分析后,其宽度为2的演化语言也是正规语言。在文章的最后小节中,结合现有的结果,对88个初等元胞自动机的演化语言复杂性做了总结。

论文目录

• 摘要
• Abstract
• 第一章 元胞自动机简介
• 1.1 引言
• 1.2 元胞自动机的定义
• 1.3 元胞自动机的分类问题
• 1.4 形式语言
• 1.5 元胞自动机的演化语言
• 第二章 基本概念和形式语言的一些性质
• 2.1 基本概念
• 2.2 正规语言
• 2.3 形式语言的一些性质
• 第三章 初等元胞自动机演化语言复杂性分析
• 3.1 计算机搜索
• 3.2 演化语言没有禁止字的初等元胞自动机
• 3.3 演化语言为有限正规的初等元胞自动机
• 3.4 演化语言为无限正规的初等元胞自动机
• 第四章 小结
• 参考文献
• 致谢