细胞自动机建模方法与应用综述

需积分: 3 14 浏览量更新于2024-08-02 收藏 223KB PDF 举报

"A Survey on Cellular Automata" 是一篇关于细胞自动机的综述文章，由Niloy Ganguly、Biplab K. Sikdar、Andreas Deutsch和Geoffrey Canright等人撰写，主要探讨了细胞自动机在不同领域的应用及其模型构建方法。细胞自动机（Cellular Automata, CA）是一种基于局部信息的分布式计算模型，它通过简单的规则和局部交互实现复杂计算。CA的特点包括局部信息处理、分散控制和普遍计算能力，这使得它们在各种应用中具有广泛的潜力。这篇文章对研究人员用于建模目的的一些方法进行了文献调查。作者们详细介绍了不同类型的细胞自动机，这些自动机可以用于模拟各种复杂的系统行为。文章还涵盖了用于预测CA全局行为的分析方法，这是从其局部配置中推断出来的关键。此外，文中深入阐述了如何从给定的全局状态反向配置CA的局部设置，这一问题通常被称为逆问题。该综述还列举了细胞自动机在多个领域的应用实例，这些领域可能包括但不限于物理学（如混沌理论和分形生成）、生物学（如生物组织和群体行为模拟）、计算机科学（如并行计算和算法设计）、社会科学（如城市规划和社会动态模拟）以及艺术和设计（如图形生成和视觉效果）等。文章提供的详尽参考文献对于新进入这个领域的研究者和已经在该领域工作的专家来说都是非常宝贵的资源，它可以帮助他们了解当前的研究趋势和技术发展。这篇综述为理解细胞自动机的基本原理、分析方法以及它们在实际问题中的应用提供了一个全面的框架，对于想要深入了解这一领域的读者来说，是一篇非常有价值的研究指南。

local rules has been one of the driving forces. To present an overview of the methodologies developed by

researchers, we broadly divide CA into two categories: additive/linear CA - that is, CA following the

constraints of xor/xnor logic for its next state function; and non-linear CA - CA which do not possess

such constraints.

A. Linear/Additive CA

Analysis of linear/additive CA is amenable to algebraic methods. Since the next state function applied

at each cell follows the operations of a Galois ﬁeld, the properties of the ﬁeld can be applied to characterize

its state transition behavior. Consequently, the linear/additive CA are also termed as GF(q) CA where

q is a prime number. The GF(2) CA - the most popular variant of GF(q) CA [71], [72] has attracted

considerable attention in recent years since it can be applied in the ﬁeld of V LSI design and test. There

have been several attempts to characterize GF(q) CA through a suitable algebraic tool. It has been

characterized using dipolynomials [123], [140]; but hybrid CA cannot be represented by dipolynomials.

CA state transition behavior has also been represented on arbitrary graphs and its behavior has been

studied based on graph-theoretic properties [237] . There are some abstract realizations of linear CA in

which the cell space is termed as an Abelian group and the state space is represented by a commutative

ring [10]. However, after this initial phase, characterization of GF(q) CA by a characteristic matrix

became a de facto standard [68], [72].

The matrix algebraic tool employing minimal and characteristic polynomials of the characteristic matrix

showed various interesting features of CA behavior. The ﬁrst important ﬁnding is the categorization of

additive CA into group and non-group CA. In a group CA each of the states has a single predecessor

which is not true for non-group CA. However, it is found that the non-group CA show uniform behavior

in which trees rooted at any cycle state are isomorphic [140]. A detailed review regarding analysis of

group and non-group CA follows.

Group CA : The most eﬀective application of null boundary group CA has been proposed in the ﬁeld

of pseudo-random pattern generation. Serra et al. [217] showed that maximum length CA - group CA

with all non-zero states lying in a single cycle - produces high quality pseudo-random patterns. It has

been established that the maximum length cycle can be produced only if the characteristic polynomial is

primitive as well as only if rule 90 and/or rule 150 is used to construct the CA [36] (rule 90 = xor(left

neighbor, right neighbor); rule 150 = xor(left neighbor, self, right neighbor)). A maximum length CA

cannot be generated by periodic boundary CA since its characteristic polynomial can be factorized [20]; a

formal proof of this was provided by Nandi [165]. The next important theoretical hurdle was the synthesis

of a CA with rule 90/150 from a given irreducible/primitive polynomial. Serra et al. used a version of

剩余29页未读，继续阅读

yangyz67

粉丝: 0
资源: 20

细胞自动机建模方法与应用综述

An Application of Non-Uniform Cellular Automata for Efficient Cryptography

Calibration of stochastic cellular automata.pdf

合成热力图的（Cellular Automata Model，CAM）是哪篇论文提出来的，论文题目是什么

输入主线速度，主线流量，匝道流量，合流区长度进行构建

netlogo里面有没有养形状的模型

基于matlab的以圆为边界的分型生长模拟代码

CAM matlab

matlab高速公路lattice

matlab元胞自动机工具包

“细胞自动机数字水印嵌入”的原理

最新资源