Chebyshev polynomials over finite fields and reversibility of σ-automata on square grids

Using number theory on function fields and algebraic number fields, we prove results about Chebyshev polynomials over finite prime fields to investigate reversibility of two-dimensional additive cellular automata on finite square grids. For example, we show that there are infinitely many primitive irreversible additive cellular automata on square grids when the base field has order two or three.     

元胞自动机可逆性研究

元胞自动机是对复杂适应系统建模的重要理论工具。可逆性是元胞自动机的一个重要属性,是模拟物理可逆空间的必要条件。本文介绍元胞自动机的基本概念、可逆性和可计算性,并介绍一维可逆元胞自动机可计算的证明思路。     

Decidability and undecidability in cellular automata

We survey results on decidability questions concerning cellular automata. Properties discussed include reversibility and surjectivity and their variants, time-symmetry and conservation laws, nilpotency and other properties of the limit set and the trace, properties chaoticity related such as sensitivity to initial conditions and mixing of the space, and dynamics from finite initial configurations. We also discuss briefly the tiling problem and its variants, and consider the influence of the dimension of the space on the decidability status of the questions.     

Modeling Local Social Migrations: A Cellular Automata Approach

In local social migrations, agents move from their initial location looking for a better local social environment. Social migrations processes do not change the number of social agents of a given type (i.e., the empirical distribution of the population) but their spatial location. Although cellular automata seems to appear as a natural approach to model of social migrations, the evolution of the configuration through a cellular automata might induce a new configuration wherein the number of agents of each type might be actually modified. This article provides a characterization of these cellular automata rules such that for any initial empirical distribution, the evolution of the configuration through a cellular automata of such class induces a new configuration with the same empirical distribution as the initial one, as required to model local social migrations. A class of sequences is defined in order to establish a sufficient condition to maintain this invariance property.     

Garden of eden configurations for 2-D cellular automata with rule 2460 N

An important problem in cellular automata theory is the reversibility of a cellular automaton which is related to the existence of Garden of Eden configurations in cellular automata. In this paper, we study new local rules for two-dimensional cellular automata over the ternary field Z₃ (the set of integers modulo three) with some of their important characteristics. We obtain necessary and sufficient conditions for the existence of Garden of Eden configurations for two-dimensional ternary cellular automata. Also by making use of the matrix representation of two-dimensional cellular automata, we provide an algorithm to obtain the number of Garden of Eden configurations for two-dimensional cellular automata defined by rule 2460 N. We present an application of the reversible two-dimensional ternary cellular automata to cryptography.     

Sand automata as cellular automata

In this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. This relation induces a compact topology for sand automata, and a new context in which sand automata are homeomorphic to cellular automata acting on a specific subshift. We show that the existing topological results for sand automata, including the Hedlund-like representation theorem, still hold. In this context, we give a characterization of cellular automata which are sand automata, and study some dynamical behaviors such as equicontinuity. Furthermore, we deal with simple sand automata. We show that the classical definition of nilpotency is not meaningful for sand automata. Then, we introduce the suitable new notion of flattening sand automata. Finally, we prove that this simple dynamical behavior is undecidable.     

Traced communication complexity of cellular automata

We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata.     

A survey of cellular automata: types,dynamics, non-uniformity and applications

Cellular automata (CAs) are dynamical systems which exhibit complex global behavior from simple local interaction and computation. Since the inception of cellular automaton (CA) by von Neumann in 1950s, it has attracted the attention of several researchers over various backgrounds and fields for modeling different physical, natural as well as real-life phenomena. Classically, CAs are uniform. However, non-uniformity has also been introduced in update pattern, lattice structure, neighborhood dependency and local rule. In this survey, we tour to the various types of CAs introduced till date, the different characterization tools, the global behavior of CAs, like universality, reversibility, dynamics etc. Special attention is given to non-uniformity in CAs and especially to non-uniform elementary CAs, which have been very useful in solving several real-life problems.

     

多选择背包问题的元胞萤火虫算法

为有效求解多选择背包问题,基于元胞自动机的原理和萤火虫算法,提出一种求解多选择背包问题的元胞萤火虫算法。将元胞及其邻居引入到算法中来保持种群的多样性,利用元胞的演化规则进行局部优化,避免算法陷入局部极值。通过对典型多选择背包问题的仿真实验和其他算法的比较,表明该算法可行有效,有良好的全局优化能力。     

基于二维CA和混沌系统的图像加密新算法

基于二维元胞自动机和Logistic混沌映射,提出了一种新的图像加密算法.该算法主要思想是采用Logistic映射设计一种非线性耦合结构来对明文像素矩阵进行置乱,然后在分析元胞自动机的混沌和密码学性质的基础上构造一个二维伪随机数矩阵来进行图像加密.仿真实验结果表明,该算法具有较大的密钥空间,对密钥具有极高的敏感性,密文具有良好的扩散和统计特性,可以有效地抵御穷举攻击、敏感性攻击以及统计攻击等.     

企业群体集聚的移动元胞自动机模拟

为了研究企业群体行为,从企业个体行为特征出发,结合元胞自动机模型,将企业本身需求特征属性、周围邻居变化影响因素和学习记忆属性等三个企业个体特征引入到元胞自动机模型,此外,在模型中赋予元胞移动属性,企业个体根据演化规则和邻域结构选择移动一步或者等待,仿真研究企业个体的三个个体特征对个体行为乃至群体行为的影响。研究结果表明,企业行为的三个个体特征对个体的行为和群体的行为都有一定的影响,其中个体的行为特征变化受周围邻居的特征变化影响。仿真实验也说明该模型与实际情况相符。     

求解绝对值距离Steiner最小树的改进元胞蚂蚁算法

绝对值距离Steiner最小树问题是在集成电路布线等领域应用广泛的属于NP难的经典组合优化问题,由于该问题的搜索空间与元胞自动机的结构相似,设计了求解绝对值距离Steiner最小树问题的改进的元胞蚂蚁算法。经大量数据实验表明,该算法要比最小生成树平均改进15%,优于多数已有的基于最小生成树的近似算法,验证了算法的实用性。     

分类回归树多吸引子细胞自动机分类方法及过拟合研究

基于多吸引子细胞自动机的分类方法多是二分类算法,难以克服过度拟合问题,在生成多吸引子细胞自动机时如何有效地处理多分类及过度拟合问题还缺乏可行的方法.从细胞空间角度对模式空间进行分割是一种均匀分割,难以适应空间非均匀分割的需要.将CART算法同多吸引子细胞自动机相结合构造树型结构的分类器,以解决空间的非均匀分割及过度拟合问题,并基于粒子群优化方法提出树节点的最优多吸引子细胞自动机特征矩阵的构造方法.基于该方法构造的多吸引子细胞自动机分类器能够以较少的伪穷举域比特数获得好的分类性能,减少了分类器中的空盆数量,在保证分类正确率的同时改善了过拟合问题,缩短了分类时间.实验分析证明了所提出方法的可行性和有效性.     

新型一维偏移耦合映像格系统及其动态特性

混沌系统具有复杂的动力学行为,但在数字系统中运行时会出现动力学特性退化的问题。元胞自动机在时间、空间上都具有离散性,能够有效减弱混沌系统在有限精度下的动力学退化问题。基于元胞自动机,提出了一种一维偏移耦合映像格系统,利用初等元胞自动机每次更新的不同状态,动态产生每个格子的耦合索引偏移量,再根据偏移量对混沌序列施加不同的扰动,然后交替切换元胞自动机的迭代规则。最后,对混沌系统的动力学特性进行对比分析以及对该系统产生的时间序列进行量化和随机性检测,仿真实验结果表明,该混沌系统周期更长,遍历性更好,产生的序列随机性更佳,在序列密码算法中有很大的应用价值。     

Spreadable cellular automata: modelling and simulations

The spreadable phenomena which describes the expansion in time of a given spatial property has been studied using models based on partial differential equations. These spreadable dynamics are generally non-linear and then difficult to simulate particularly in two dimensions. In this article, we propose cellular automata (CA) models as an alternative modelling tool that can easily simulate spreadable systems. CA are capable of describing complex systems based on simple evolution rules, which provide numerical schemes directly implemented on computers without approximation or rounding errors. We design local CA dynamics which allow us to maintain a spatial property on non-decreasing subdomains. Several numerical results are performed to illustrate spreadable phenomena. The simulation results corroborate the general shape theory that exhibits the convergence to a specific domain independently on initial conditions.     

On Incentives and Updating in Agent Based Models

This paper introduces the concept of incentive based asynchronous updating in which the order of updating is determined by incentives. Previously, asynchronous updating has been shown to yield greater stability than synchromous updating for a variety of dynamical systems. However, in those models the order of updating is random. When incentives determine the ordering, the dynamics and end states change. For a conformity model on a two dimensional cellular automata, incentive based asynchronous updating yields greater linear disparity. Fot the game of life, it results in much greater sensitivity to initial conditions.     

The ergodic theory of cellular automata

Ergodic theory is the study of how a dynamical system transforms the information encoded in an invariant probability measure. This article reviews the major recent results in the ergodic theory of cellular automata.     

Progresses in the analysis of stochastic 2D cellular automata: A study of asynchronous 2D minority

Cellular automata are often used to model systems in physics, social sciences, biology that are inherently asynchronous. Over the past 20 years, studies have demonstrated that the behavior of cellular automata drastically changes under asynchronous updates. Still, the few mathematical analyses of asynchronism focus on 1D probabilistic cellular automata, either on single examples or on specific classes. As for other classic dynamical systems in physics, extending known methods from 1D to 2D systems is a long lasting challenging problem.In this paper, we address the problem of analyzing an apparently simple 2D asynchronous cellular automaton: 2D Minority where each cell, when fired, updates to the minority state of its neighborhood. Our simulations reveal that in spite of its simplicity, the minority rule exhibits a quite complex response to asynchronism. By focusing on the fully asynchronous regime, we are however able to describe completely the asymptotic behavior of this dynamics as long as the initial configuration satisfies some natural constraints. Besides these technical results, we have strong reasons to believe that our techniques relying on defining an energy function from the transition table of the automaton may be extended to the wider class of threshold automata. ²     

Reversible computing and cellular automata—A survey

Reversible computing is a paradigm where computing models are defined so that they reflect physical reversibility, one of the fundamental microscopic physical property of Nature. In this survey/tutorial paper, we discuss how computation can be carried out in a reversible system, how a universal reversible computer can be constructed by reversible logic elements, and how such logic elements are related to reversible physical phenomena. We shall see that, in reversible systems, computation can often be carried out in a very different manner from conventional (i.e., irreversible) computing systems, and even very simple reversible systems or logic elements have computation- or logical-universality. We discuss these problems based on reversible logic elements/circuits, reversible Turing machines, reversible cellular automata, and some other related models of reversible computing.     

软件可信性演化的移动元胞自动机模拟

演化是软件可信性的核心问题。为了研究在动态、开放、多变环境下,干扰对软件可信性的影响,在分析软件系统可信性传递过程的基础上,结合元胞自动机机理和耗散理论,构建基于用户视角的软件系统可信性演化的移动元胞自动机仿真模型,仿真研究了软件系统在受到干扰的情境下,软件可信性的变化过程。研究表明,软件系统在受到干扰的环境下,当运行状态发生变化时,其可信性评价值降低,在经历了多次干扰后,系统可信性评价值最终稳定,这为动态评价、预测软件系统可信性提供了一个新的模型与方法。