自组织过程的随机元胞自动机模拟

将随机机制引入元胞自动机，建立了若干自组织过程的随机元胞自动机模型；编制了Ｗｉｎｄｏｗｓ环境下的通用元胞自动机程序，成功地模拟了粒子扩散、沙堆崩塌、分形凝聚、晶体生长等动态过程。     

交通元胞自动机类型的研究

详细地介绍了元胞自动机的基本定义及特点,着重论述了三种不同类型的交通元胞自动机及其元胞状态更新的原则,探讨了其应用上的区别,并对不同元胞自动机所采用的随机选择过程与同时更新模型做了比较。     

基于地理空间实体的矢量元胞自动机研究

元胞自动机是能模拟复杂行为的离散动力学模型，GIS与元胞自动机的集成对于模拟地理时空过程具有很大的优势。但是标准CA的一些限制因素如空间尺度、精度及数据量问题、邻居定义等制约了其模拟真实世界的能力。本文通过分析地理现象和元胞自动机之间的关系，从元胞及状态、元胞空间、邻居、转换规则、离散时间五个方面对标准元胞自动机的组成部分进行了扩展，构建了在不规则的地理空间中基于地理实体的元胞自动机模型，同时提出了一个通用的基于地理实体的元胞自动机模型和地理信息系统集成的框架。     

基于元胞自动机的拓扑排序算法

目的 利用元胞自动机的特性,找到一种新的拓扑排序算法.方法 将AOV网构造成一个元胞自动机模型,采用经过改造的邻接链表作为元胞的数据结构,并在其中引入随机编号项,所有元胞依据随机编号顺序地遵守演化规则进行演化,实现拓扑排序.结果 利用元胞自动机的时空局部规则和并行计算特性,设计并验证了拓扑排序算法.结论 与传统算法相比本算法在时间、空间复杂性上都有较大改善,并且在应用元胞自动机理论解决图的问题方面有所贡献.     

基于元胞自动机的人员疏散行为模拟研究

公共场所人员疏散已经成为公共安全研究的重要问题,元胞自动机可以对复杂现象进行仿真。采用元胞自动机建模,确定了元胞空间和元胞状态,对疏散过程中疏散人员建立了疏散行为规则,着重探讨了从众行为和小团体行为对疏散结果的影响,并对人员疏散过程进行仿真,对元胞自动机模拟人员疏散行为进行了分析研究。     

地理元胞自动机研究综述

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

标准元胞自动机模型的缺陷及拓展研究

具备时空计算特征的元胞自动机模型（CA）与GIS集成将极大促进GIS对地理过程的模拟能力。标准元胞自动机在元胞形态、邻居规则等方面的定义存在极大限制，制约了元胞自动机对真实世界的模拟和应用能力。论文充分研究了空间模型与元胞邻居描述的关系，发现元胞邻居在空间关系上存在拓扑邻接、空间邻近和复杂相离三种关系，传统思路的模型扩展很难完全解决CA的局限性，尤其是复杂相离关系。为此，论文在面向对象的思想基础上提出了基于地理实体的元胞自动机概念模型。     

摩擦层形成的元胞自动机模拟

建立了汽车摩擦材料在摩擦过程中摩擦层形成的变时间步长的二维和三维元胞自动机模型,模拟了磨屑运动的变化状态与摩擦材料的表面形貌。用二维元胞自动机模型模拟了无磨损条件下摩擦材料表面的摩擦层的形成过程,可以得到磨屑沿摩擦力方向运动并聚集的图像。用三维元胞自动机模型模拟了有磨损时摩擦材料表面的摩擦层的形成过程,可以得到摩擦材料在不同厚度的磨屑运动和聚集的动态图像。通过元胞自动机模拟可以确定摩擦层形成的机制与磨屑的运动和受阻于钢纤维、陶瓷纤维或磨粒并聚集有关,也证明了在摩擦层的研究中元胞自动机法是一个理想的模拟方法。     

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

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

基于模糊元胞自动机的复杂图案、纹理生成实现

结合模糊规则和元胞自动机的机理,分析了模糊元胞自动机的基本原理,根据元胞自动机的不同构形,提出多种模糊元胞自动机演化规则,并根据这些基本规则,分别用3邻元、5邻元以及9邻元进行元胞状态更新,生成了多颜色\复杂、漂亮的图案和织物纹理,其结果在针织织物设计中意义重大.     

Local interactions predict large-scale pattern in empirically derived cellular automata.

An important unanswered question in ecology is whether processes such as species interactions that occur at a local scale can generate large-scale patterns seen in nature. Because of the complexity of natural ecosystems, developing an adequate theoretical framework to scale up local processes has been challenging. Models of complex systems can produce a wide array of outcomes; therefore, model parameter values must be constrained by empirical information to usefully narrow the range of predicted behaviour. Under some conditions, spatially explicit models of locally interacting objects (for example, cells, sand grains, car drivers, or organisms), variously termed cellular automata or interacting particle models, can self-organize to develop complex spatial and temporal patterning at larger scales in the absence of any externally imposed pattern. When these models are based on transition probabilities of moving between ecological states at a local level, relatively complex versions of these models can be linked readily to empirical information on ecosystem dynamics. Here, I show that an empirically derived cellular automaton model of a rocky intertidal mussel bed based on local interactions correctly predicts large-scale spatial patterns observed in nature.     

构件化嵌入式软件设计的能耗性质分析与验证

从嵌入式软件设计模型层对构件化实时嵌入式软件系统中能耗相关性质进行研究,包括:扩展了实时接口自动机在能耗语义方面的描述能力,通过引入状态能量消耗率,建立了能耗接口自动机形式化模型以及自动机网络,用以建模嵌入式软件设计阶段系统构件及其构件组合的能耗行为特征;对能耗接口自动机网络的状态空间进行了形式化分析,构造了相应的可兼容整型空间的可达图,并在此基础上给出了最小能耗计算和最大能耗验证的算法.     

二维二方向有限自动机的识别能力研究

研究了3种有限自动机,即二维二方向的确定型、非确定型以及Las Vegas有限自动机.证明存在语言能被二维二方向的Las Vegas有限自动机识别,但不能被相应的确定型有限自动机识别;存在语言能被二维二方向的非确定型有限自动机识别,但不能被相应的Las Vegas有限自动机识别.研究结果表明,二维二方向的Las Vegas有限自动机所识别的语言真包含确定型有限自动机所识别的语言;二维二方向的非确定型有限自动机所识别的语言真包含Las Vegas有限自动机所识别的语言.     

Fuzzy树自动机的等价性

在给出模糊树自动机概念的基础上,讨论了模糊树自动机与传统字符自动机、模糊有限自动机相类似的性质,即指确定性模糊树自动机与非确定性的模糊树自动机的等价性、FNBTA与FNTTA 等价,及FDBTA和FNBTA等价;这为模糊树自动机的进一步研究奠定了基础.     

CFSM模型的有限自动机语义

研究CFSM模型的自动机语义,提出了一种从CFSM到自动机转换的算法。该算法的核心思想是构造一个包含控制自动机、输入自动机、输出自动机的有限状态自动机系统,利用自动机的同步性模拟CFSM的异步行为。本文的工作为进一步利用自动机理论和工具对CFSM模型进行分析和验证奠定了基础。     

非确定型有穷自动机的极小化

利用自动机状态集上的等价关系对自动机的状态集进行极小化, 从而得到与原自动机功能等价的极小化自动机. 通过两台确定型有穷自动机（DFA）的连接, 构造一台非确定型有穷自动机（NFA）. 利用这两台确定型有穷自动机状态集上的等价关系, 可以构造这台非确定型有穷自动机状态集上的等价关系, 从而对这台非确定型有穷自动机进行极小化. 结果表明这台非确定型有穷自动机的极小化自动机的状态复杂 度, 不大于对那两台确定型有穷自动机的极小化自动机进行连接得到的非确定型有穷自动机的状态复杂度; 并且自动机在等价关系基础上进行极小化时不改变识别语言.     

Programmable and autonomous computing machine made of biomolecules.

Devices that convert information from one form into another according to a definite procedure are known as automata. One such hypothetical device is the universal Turing machine, which stimulated work leading to the development of modern computers. The Turing machine and its special cases, including finite automata, operate by scanning a data tape, whose striking analogy to information-encoding biopolymers inspired several designs for molecular DNA computers. Laboratory-scale computing using DNA and human-assisted protocols has been demonstrated, but the realization of computing devices operating autonomously on the molecular scale remains rare. Here we describe a programmable finite automaton comprising DNA and DNA-manipulating enzymes that solves computational problems autonomously. The automaton's hardware consists of a restriction nuclease and ligase, the software and input are encoded by double-stranded DNA, and programming amounts to choosing appropriate software molecules. Upon mixing solutions containing these components, the automaton processes the input molecule via a cascade of restriction, hybridization and ligation cycles, producing a detectable output molecule that encodes the automaton's final state, and thus the computational result. In our implementation 1012 automata sharing the same software run independently and in parallel on inputs (which could, in principle, be distinct) in 120 microl solution at room temperature at a combined rate of 109 transitions per second with a transition fidelity greater than 99.8%, consuming less than 10-10 W.     

非洲猪瘟舍内传播元胞自动机仿真研究

为了研究非洲猪瘟在封闭式猪舍内传播的规律,本文通过引入SI模型,并在此基础上进行改进,结合猪舍内猪只的移动规律及个体体质的差异,分析猪舍内猪只感染非洲猪瘟的概率;设计猪只个体接触后的感染规则,构建元胞自动机模型进行仿真,模拟非洲猪瘟在猪舍的传播情况;通过将元胞自动机模拟的非洲猪瘟的传播仿真结果与传统SI模型的传播数据进行对比分析。结果表明,元胞自动机仿真非洲猪瘟舍内传播能够与传统的SI模型传播数据可以实现较好的拟合,拟合度为0.96,同时使用元胞自动机作为非洲猪瘟的传播模型在预测方面具有优势,可以通过迭代对传播过程可视化,进而实时预测非洲猪瘟在密闭猪舍的传播轨迹,为相关传染病的仿真研究提供了理论指导。     

基于Langton参数的一维DNA元胞自动机的涌现计算

通过引入DNA元胞自动机的概念, 利用总和规则研究基于Langton参数的半径为3的一维DNA元胞自动机, 得到了Wolfram的4个等级. 结果表明, 随着参数λ的不同, DNA元胞自动机展现出不同的结构, 当λ介于一个中间值时动态行为达到最大的复杂性, 随着λ的进一步增大, 复杂结构逐渐被随机结构所取代.     

Algorithm for repairing the damaged images of grain structures obtained from the cellular automata and measurement of grain size

Computational models are developed to create grain structures using mathematical algorithms based on the chaos theory such as cellular automaton, geometrical models, fractals, and stochastic methods. Because of the chaotic nature of grain structures, some of the most popular routines are based on the Monte Carlo method, statistical distributions, and random walk methods, which can be easily programmed and included in nested loops. Nevertheless, grain structures are not well defined as the results of computational errors and numerical inconsistencies on mathematical methods. Due to the finite definition of numbers or the numerical restrictions during the simulation of solidification, damaged images appear on the screen. These images must be repaired to obtain a good measurement of grain geometrical properties. Some mathematical algorithms were developed to repair, measure, and characterize grain structures obtained from cellular automata in the present work. An appropriate measurement of grain size and the corrected identification of interfaces and length are very important topics in materials science because they are the representation and validation of mathematical models with real samples. As a result, the developed algorithms are tested and proved to be appropriate and efficient to eliminate the errors and characterize the grain structures.