122号元胞自动机的演化语言复杂性

研究了122号初等元胞自动机的演化语言,证明了其宽度为1的演化语言是正规的,宽度大于1的演化语言不是正规的。结果表明:仅用有限自动机是无法接受由122号初等元胞自动机产生的演化语言。     

126号初等元胞自动机的演化语言复杂性

元胞自动机是结构简单但行为复杂多样的离散动力系统.通过形式语言和符号动力学工具研究了126号初等元胞自动机的演化语言,证明了宽度大于1的演化语言不是上下文无关语言,而是上下文有关语言.     

初等元胞自动机在加法规则下的演化

本文总结了经典元胞自动机模型理论,并在此基础上定义了初等元胞自动机的加法规则。引入代数方法探讨了初等元胞自动机在其中一种加法规则下的演化性质,由此推出了一些相关性的结论。它是初等元胞自动机在其加法规则下所特有的,使其在模拟事物时更具有方向性,不但丰富了初等元胞自动机的理论,而且为研究元胞自动机的理论提供了可行的方案。为了便于直观的验证某些结论,本文利用了初等元胞自动机的状态迁移图来加以描述它的演化过程。     

基于卡诺图初等元胞自动机的演化规则

依据初等元胞自动机演化规则的特点,借助卡诺图化简,导出初等元胞自动机演化规则的函数形式。进一步利用推导出的演化规则的函数形式,给出演化规则90和演化规则184的演化定理及相关定理的证明。     

126号初等元胞自动机的演化复杂性

用形式语言理论和符号动力学对126号初等元胞自动机的演化复杂性进行研究.证得其1-演化语言为正规的,而n≥2时其n-演化语言为非正规的.     

确定的有限元胞自动机的两个性质

提出了确定的有限元胞自动机的概念,通过对演化构形的惟一性特征的分析.证明了确定的有限元胞自动机的状态演化最终处于稳定状态或者循环状态;具有相同演化结果的状态构成等价关系两个性质.利用初等元胞自动机对其进行了验证,在此基础上,对元胞自动机的四个普遍性分类进行了三个层次的探讨.     

7号初等元胞自动机生成的时间序列的复杂性分析

使用禁止字理论、计算机搜索和符号动力学的方法对7号初等元胞自动机生成的时间序列从形式语言的角度进行复杂性分析,确定了禁止字集及其Chomsky层次,确定了演化语言的一个精简的Chomsky层次,并由此得到了时间序列的完整描述.     

126号初等元胞自动机时间序列的非周期性

元胞自动机是结构简单但行为复杂多样的离散动力系统.本文以模拟90号初等元胞自动机为基础,证明了126号初等元胞自动机下任意有限初始条件迭代产生的时间序列是非周期的.     

从粒子角度研究164号元胞自动机的极限语言复杂性

通过定义164号元胞自动机的基本粒子,找到了粒子的逆演化规律,从而完全确定了其极限语言,并证明了164号元胞自动机的极限语言是正规的。结果表明:用有限自动机就可以接收该极限语言。     

元胞自动机混沌的一个必要条件

提出了元胞自动机混沌的一个必要条件,给出了判断初等元胞自动机是否满足这一条件的算法.并用此条件证明了一种非线性元胞自动机———投票规则是混沌的.     

A complexity analysis of the elementary cellular automaton of rule 122

S. Wolfram initiated the use of formal languages and automata theory in study of cellular automata (CAs). By means of extensive experiments with computer, he classified all CAs into four classes and conjectured that the limit languages of the third class of CAs, which produce chaotic aperiodic behavior, are not regular. Using symbolic dynamics and formal languages, we prove that the limit language of the elementary CA of rule 122 is neither regular nor context-free.     

一种一维细胞自动机的分类

讨论了基本细胞自动机的一种扩展模型,通过二元矩阵展现了局部规则与全局演化的关系.利用矩阵的秩对这类细胞自动机进行了计算机实验分类.     

基于元胞自动机的大学课程教学模拟

用232号初等元胞自动机规则和教学策略、响应概率及倾向概率等参数控制规则建立了大学课程教学的元胞自动机模型。模拟研究了大学课程教学的复杂性,教学策略、响应概率、倾向概率及初始条件的影响,教学设计的优化等。结果表明,该模型符合大学课程教学实际,可以作为大学课程教学的数值模拟工具。     

细胞自动机及其理论研究进展

细胞自动机固有的组成单元的简单性,单元之间作用的局部性和信息处理的高度并行性,并表现出复杂的全局特性等特点使得其广泛应用于物理模型模拟、密码学和内建式自测试等领域。本文简述了细胞自动机的基本概念,研究了细胞自动机的分析理论和细胞自动机的综合理论。     

基于蚁群算法的细胞自动机优化及其在电路测试中的应用

细胞自动机在电路设计、计算机安全等领域有广泛的应用.首先通过使用蚁群算法实现对细胞自动机结构的优化配置,从而产生具有较强随机性的伪随机数序列;其次,把细胞自动机应用于数字电路的测试,利用经优化后的二维细胞自动机来生成测试矢量.实验结果表明,经过蚁群算法优化之后得到的细胞自动机能够产生随机性较强的伪随机数序列,在数字电路测试的应用中能够提高故障覆盖率.     

细胞自动机的演化与计算理论’

本文介绍一细胞自动机的基础原理，讨论了细胞自动演化位形序列与形式语言的等价性，并给出９０规则与１５０规则的正则语言集，则时还建立了Ｔｕｒｉｎｇ机仿真９０规则的程序并给出相应的状态转移图。     

地理元胞自动机研究综述

从地理元胞自动机的应用范围、地理元胞自动机转换规则的获取、地理元胞自动机空间划分、元胞自动机与GIS的集成等方面回顾了地理元胞自动机模型的研究,对地理元胞自动机模型研究的发展趋势进行了分析,认为地理元胞自动机模型研究在以下几个方面需要进一步深入：（1）应用范围应进一步扩大;（2）在确定地理元胞自动机的转换规则时应综合考虑自然因素和社会经济因素;（3）应加强地理元胞自动机与多智能体系统的集成研究;（4）应加强对地理元胞自动机的尺度划分及尺度效应的研究;（5）应进一步深化地理元胞自动机与GIS的集成研究。     

基于细胞自动机的公钥密码体制研究

为了解决高速实时信息传输的瓶颈问题,该文提出了一种基于细胞自动机理论的公钥密码算法.该算法以n个一维可逆细胞自动机为私钥,由它们构造出的二维Moore型不可逆的细胞自动机为公钥组成公钥密码体制.该算法实现简单,易于VLSI(超大规模集成电路)实现,有效地解决了复杂密码算法在高速实时信息传输时带来的瓶颈现象.