论文题目: 元胞自动机生成的时间序列的复杂性研究
论文类型: 博士论文
论文专业: 应用数学
作者: 秦大康
导师: 谢惠民
关键词: 初等元胞自动机,时间序列,禁止字,形式语言,演化语言,层次
文献来源: 苏州大学
发表年度: 2005
论文摘要: 元胞自动机是自然界许多复杂系统的理想化数学模型,它可以模拟许多自然现象与生命现象,大量未解决的问题为这个困难而有趣的领域展现了广阔的前景。 自von Neumann首次提出元胞自动机的思想至今已有半个世纪,学者们对元胞自动机进行了大量的研究,然而现在对元胞自动机仍然缺少有效的数学方法,严格的数学结果也很少。本文探求一种新的研究元胞自动机的方法,使用禁止字理论、计算机搜索和符号动力学的方法对于256个初等元胞自动机生成的时间序列(只观察一个位点上的演化所得到的序列)进行复杂性分析。借助时间序列所具有的特性通过研究它的禁止字来研究演化语言(本文所指的演化语言如无特别标注都是指宽度为1的时间序列所组成的语言),确定了大多数初等元胞自动机生成的时间序列所处的Chomsky层次以及严格的数学表达式。 在对初等元胞自动机时间序列的禁止字分析之后,按照它们演化语言的复杂程度分为以下四类:第Ⅰ类为满射,第Ⅱ类为有限补正规语言,第Ⅲ类为无限补正规语言,第Ⅳ类很有可能是非正规语言。 第Ⅰ类情况中的初等元胞自动机没有禁止字,其宽度1的演化语言为最大可能的正规语言,并且这一类中部分元胞自动机的任意宽度演化语言都是正规的。 第Ⅱ类情况中的初等元胞自动机只有有限多个禁止字,因此其宽度1的演化语言为有限补正规语言。 第Ⅲ类情况中的初等元胞自动机有无限多个禁止字,但禁止字集是正规语言,经过理论分析知道其演化语言为无限补正规语言。此类情况中一个代表性的例子是27号初等元胞自动机。 第Ⅳ类情况中的初等元胞自动机也有无限多个禁止字,但是它们的演化语言很有可能不是正规语言,这类情况比前三种情况复杂的多,对这一类初等元胞自动机的讨论尚未全部完成。本文给出了其中56号初等元胞自动机的宽度为1的演化语言是上下文无关语言的详细证明,并给出了严格的数学表达式。
论文目录:
摘要
Abstract
目录
苏州大学博士学位论文详细摘要
第一章 元胞自动机简介
1．1 引言
1．2 元胞自动机的定义
1．3 元胞自动机的分类问题
1．4 元胞自动机的极限语言和演化语言
第二章 时间序列的复杂性分析
2．1 引言
2．2 禁止字
2．3 计算机搜索
2．4 第Ⅰ类：满射
2．4．1 子类Ⅰ．1
2．4．2 子类Ⅰ．2
2．5 第Ⅱ类：有限补正规情况
2．6第Ⅲ类：无限补正规情况
2．7 第Ⅳ类：非正规情况
2．8 讨论
第三章 27号元胞自动机
3．1 引言
3．2 定理3．1的证明
第四章 56号元胞自动机
4．1 引言
4．2 用计算机进行搜索的实验结果
4．3 主要结果
4．4 定理4．1的证明
4．5 定理4．2和定理4．3的证明
附录A 形式语言与自动机理论介绍
A．1 引言
A．2 基本概念
A．3 四类语言与四类自动机
A．4 正规语言与有限自动机
参考文献
发表文章目录
致谢
发布时间: 2006-03-24
参考文献
- [1].复杂系统的元胞自动机方法研究[D]. 曹兴芹.华中科技大学2006
- [2].元胞自动机原理及其在密码学的应用研究[D]. 平萍.南京理工大学2009
- [3].动基座下的运动目标检测技术研究[D]. 陆牧.中国科学院长春光学精密机械与物理研究所2017
- [4].金融复杂系统建模及动力学机制研究[D]. 丁竞渊.上海大学2011
- [5].肿瘤生长过程形态模拟及相关技术研究[D]. 甘建红.西南交通大学2009
- [6].多层元胞自动机加密算法的研究与实现[D]. 张星.南京理工大学2016
- [7].多传播因素的复杂网络病毒传播及免疫策略研究[D]. 王亚奇.南京邮电大学2011
- [8].智能交通监控中运动目标检测与跟踪算法研究[D]. 崔雨勇.华中科技大学2012
- [9].进化交通网络模型及悖论、鲁棒性分析[D]. 赵春雪.大连理工大学2013
- [10].第2类装配平衡问题的多规则组合优化算法研究[D]. 李明.武汉科技大学2015
相关论文
- [1].元胞单元法理论研究及程序设计[D]. 杨吉新.武汉理工大学2002
- [2].复杂性理论及其在城市系统研究中的应用[D]. 吴晓军.西北工业大学2005