Classifying cellular automata automatically: Finding gliders,filtering, and relating space‐time patterns,attractor basins,and the Z parameter

Cellular automata (CA) rules can be classified automatically for a spectrum of ordered, complex, and chaotic dynamics by a measure of the variance of input‐entropy over time. Rules that support interacting gliders and related complex dynamics can be identified, giving an unlimited source for further study. The distribution of rule classes in rule‐space can be shown. A byproduct of the method allows the automatic “filtering” of CA space‐time patterns to show up gliders and related emergent configurations more clearly. The classification seems to correspond to our subjective judgment of space‐time dynamics. There are also approximate correlations with global measures on convergence in attractor basins, characterized by the distribution of in‐degree sizes in their branching structure, and to the rule parameter, Z. Based on computer experiments using the software Discrete Dynamics Lab (DDLab), this article explains the methods and presents results for 1D CA. © 1999 John Wiley & Sons, Inc.     

Advances in the study of elementary cellular automata regular language complexity

Cellular automata (CA) are discrete dynamical systems that, out of the fully local action of its state transition rule, are capable of generating a multitude of global patterns, from the trivial to the arbitrarily complex ones. The set of global configurations that can be obtained by iterating a one‐dimensional cellular automaton for a finite number of times can always be described by a regular language. The size of the minimum finite automaton corresponding to such a language at a given time step provides a complexity measure of the underlying rule. Here, we study the time evolution of elementary CA, in terms of such a regular language complexity. We review and expand the original results on the topic, describe an alternative method for generating the subsequent finite automata in time, and provide a method to analyze and detect patterns in the complexity growth of the rules. © 2015 Wiley Periodicals, Inc. Complexity 21: 267–279, 2016     

Glider-based computing in reaction-diffusion hexagonal cellular automata

A three-state hexagonal cellular automaton, discovered in [Wuensche A. Glider dynamics in 3-value hexagonal cellular automata: the beehive rule. Int J Unconvention Comput, in press], presents a conceptual discrete model of a reaction-diffusion system with inhibitor and activator reagents. The automaton model of reaction-diffusion exhibits mobile localized patterns (gliders) in its space–time dynamics. We show how to implement the basic computational operations with these mobile localizations, and thus demonstrate collision-based logical universality of the hexagonal reaction-diffusion cellular automaton.     

Fuzzy automata and life

Boolean cellular automata may be generalized to fuzzy automata in a consistent manner. Several fuzzy logics are used to create 1‐dimensional automata and also 2‐dimensional automata that generalize the game of life. These generalized automata are investigated and compared to their Boolean counterparts empirically and using rule entropy and repeated input response functions. Fuzzy automata offer new mechanisms for classification of classical automata and can be used for insight into their qualitative behavior. © 2002 Wiley Periodicals, Inc.     

Characteristic parameters and classification of one-dimensional cellular automata

We present definitions of characteristic parameters and discuss a classification of one-dimensional cellular automata. The parameters: probability of active sites, capacity dimension and spreading rate of difference patterns are defined on the image of the configuration space of all site states under a rule function of time evolution. On study of 2-state, 3-neighbor cellular automata we propose a new classification scheme of the rules, which gives quantitative grounds for the Wolfram's phenomenological classification.     

Prioritized Composition With Exclusion and Generation for the Interaction and Control of Discrete Event Systems

Interaction of multiple discrete event systems (DESs) represented as automata are carried out using composition operations. These operations on automata enforce concurrency, wherein an event exists in the composed automaton if it exists in the participating states of the interacting automata possessing the event in their event set. Heymann generalized this by introducing event priorities, wherein an event exists in the composed automaton if it exists in the participating state of the interacting automata having priority over the event. For two interacting automata P and Q, while prioritized composition can model the P, Q, AND, and OR boolean interactions, it cannot model boolean interactions which require exclusivity of participation, namely, “exclusive P”, “exclusive Q”, “exclusive P or exclusive Q”, “exclusive P and exclusive Q”. In order to also model these additional interactions we propose a generalization of prioritized composition by introducing an exclusivity set besides the existing priority sets. The resulting composition is called prioritized composition with exclusion. We also introduce prioritized composition with exclusion and generation that allows for all sixteen boolean modes of interaction possible when two automata interact. This is done by the further introduction of a nor-generative set. This event set together with the two priority sets and an exclusivity set makes it possible to model eight additional boolean interactions which do not require either of the interacting automata to participate for the event to be enabled in the composed automaton. The applicability of these interactions to decentralized supervisory decision fusion and in composing the rules based model of systems has been illustrated.     

Guidelines for dynamics‐based parameterization of one‐dimensional cellular automata rule spaces

As paradigmatic complex systems, various studies have been done in the context of one‐dimensional cellular automata (CA) on the definition of parameters directly obtained from their transition rule, aiming at the help they might provide to forecasting CA dynamic behavior. Out of the analysis of the most important parameters available for this end, as well as others evaluated by us, a set of guidelines is proposed that should be followed when defining a parameter of that kind. Based upon the guidelines, a critique of those parameters is made, which leads to a set of five that jointly provide a good forecasting set; two of them were drawn from the literature and three are new ones defined according to the guidelines. By using them as a heuristic in the evolutionary search for CA of a predefined computational behavior, good results have been obtained, exemplified herein by the evolutionary search for CA that perform the Synchronization Task. © 2001 John Wiley & Sons, Inc.     

Quantum calculation of thermal effect in quantum‐dot cellular automata

We present a theoretical study of thermal effect in quantum‐dot cellular automata (QCA). An extended Hubbard‐type model for the Hamiltonian of the QCA arrays, and canonical distribution were used to obtain thermal average of polarization for the QCA cells. A full‐basis quantum method has been used for the calculation of response function for a two‐ and a three‐cell array system. Each cell is composed of four dots located at the corners of the cells. Results show that the nonlinear behavior of the response function functions decay with the temperature as well as with the number of cells in the array. © 2005 Wiley Periodicals, Inc. Complexity 10: 73–78, 2005     

Self‐organizing traffic lights at multiple‐street intersections

The elementary cellular automaton following rule 184 can mimic particles flowing in one direction at a constant speed. Therefore, this automaton can model highway traffic qualitatively. In a recent paper, we have incorporated intersections regulated by traffic lights to this model using exclusively elementary cellular automata. In such a paper, however, we only explored a rectangular grid. We now extend our model to more complex scenarios using an hexagonal grid. This extension shows first that our model can readily incorporate multiple‐way intersections and hence simulate complex scenarios. In addition, the current extension allows us to study and evaluate the behavior of two different kinds of traffic‐light controller for a grid of six‐way streets allowing for either two‐ or three‐street intersections: a traffic light that tries to adapt to the amount of traffic (which results in self‐organizing traffic lights) and a system of synchronized traffic lights with coordinated rigid periods (sometimes called the “green‐wave” method). We observe a tradeoff between system capacity and topological complexity. The green‐wave method is unable to cope with the complexity of a higher‐capacity scenario, while the self‐organizing method is scalable, adapting to the complexity of a scenario and exploiting its maximum capacity. Additionally, in this article, we propose a benchmark, independent of methods and models, to measure the performance of a traffic‐light controller comparing it against a theoretical optimum. © 2011 Wiley Periodicals, Inc. Complexity, 2012     

基于员工行为差异的元胞自动机演化模拟与机制设计

提出了企业员工的正行为、零行为和负行为概念,分析了员工中不同行为间的相互影响.对传统元胞自动机方法进行了改进,建立了基于员工传播性和保持性的元胞自动机模型,并对员工不同的初始比例、不同的行为传播性和保持性以及企业不同奖励和惩罚性政策下的员工行为演化进行了模拟,得到了一些合理和有益的结论,并对不同情形下的人员管理提供了针对性建议.     

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

Symbolic dynamics of cellular automata is introduced by coarse-graining the temporal evolution orbits. Evolution languages are defined. By using the theory of formal languages and automata, the complexity of evolution languages of the elementary cellular automaton of rule 146 is studied and it is proved that its width 1-evolution language is regular, but for every n ≥ 2 its width n-evolution language is not context-free but context-sensitive. Also, the same results hold for the equivalent （under conjugation） elementary cellular automaton of rule 182.     

多目标0-1规划问题的元胞狼群优化算法研究

针对多目标0-1规划问题,首先基于元胞自动机原理和人工狼群智能算法,提出一种元胞狼群优化算法,该算法将元胞机的演化规则与嚎叫信息素更新规则、人工狼群更新规则进行组合,采用元胞及其邻居来增强搜索过程的多样性和分布性,使人工头狼在元胞空间搜索的过程中,增强了人工狼群算法的全局搜索能力,并获得更多的全局非劣解;其次结合多目标0-1规划模型对元胞狼群算法进行了详细的数学描述,定义了人工狼群搜索空间、移动算子、元胞演化规则和非劣解集更新规则,并给出了元胞狼群算法的具体实现步骤;最后通过MATLAB软件对3个典型的多目标0-1规划问题算例进行解算,并将解算结果与其它人工智能算法的结果进行比较,结果表明:元胞狼群算法在多目标0-1规划问题求解方面可获得更多的非劣解集和更优的非劣解,并具有较快的收敛速度和较好的全局寻优能力。     

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

Cellular automata are the discrete dynamical systems of simple construction but with complex and varied behaviors. In this paper, the elementary cellular automaton of rule 22 is studied by the tools of formal language theory and symbolic dynamics. Its temporal evolution orbits are coarse-grained into evolution sequences and the evolution languages are defined. It is proved that for every n≥2 its width n evolution language is not regular.     

Algebraic properties of some quadratic dynamical systems

We study the interrelation between the algebraic properties and the dynamical behavior of elementary cellular automata and other deterministic quadratic dynamical systems. The examples presented indicate that complex behavior, often observed in these systems, can be connected to the nonassociativity of algebraic structures on which systems evolve.     

Algebraic properties of some quadratic dynamical systems

We study the interrelation between the algebraic properties and the dynamical behavior of elementary cellular automata and other deterministic quadratic dynamical systems. The examples presented indicate that complex behavior, often observed in these systems, can be connected to the nonassociativity of algebraic structures on which systems evolve.     

On the dynamics and recursive properties of multidimensional symbolic systems

We study the (sub)dynamics of multidimensional shifts of finite type and sofic shifts, and the action of cellular automata on their limit sets. Such a subaction is always an effective dynamical system: i.e. it is isomorphic to a subshift over the Cantor set the complement of which can be written as the union of a recursive sequence of basic sets. Our main result is that, to varying degrees, this recursive-theoretic condition is also sufficient. We show that the class of expansive subactions of multidimensional sofic shifts is the same as the class of expansive effective systems, and that a general effective system can be realized, modulo a small extension, as the subaction of a shift of finite type or as the action of a cellular automaton on its limit set (after removing a dynamically trivial set). As applications, we characterize, in terms of their computational properties, the numbers which can occur as the entropy of cellular automata, and construct SFTs and CAs with various interesting properties.     

Remark on cellular automata and shift preserving maps

The main goal of this work is to show an extension of well known Hedlund’s theorem which states that in the Cantor topology the cellular automata are the continuous shift preserving maps. This extension maintains the topological structure and uses the concept of barriers of Set Theory to generalize the notion of local rule in the definition of cellular automata.     

A novel image encryption algorithm using chaos and reversible cellular automata

In this paper, a novel image encryption scheme is proposed based on reversible cellular automata (RCA) combining chaos. In this algorithm, an intertwining logistic map with complex behavior and periodic boundary reversible cellular automata are used. We split each pixel of image into units of 4 bits, then adopt pseudorandom key stream generated by the intertwining logistic map to permute these units in confusion stage. And in diffusion stage, two-dimensional reversible cellular automata which are discrete dynamical systems are applied to iterate many rounds to achieve diffusion on bit-level, in which we only consider the higher 4 bits in a pixel because the higher 4 bits carry almost the information of an image. Theoretical analysis and experimental results demonstrate the proposed algorithm achieves a high security level and processes good performance against common attacks like differential attack and statistical attack. This algorithm belongs to the class of symmetric systems.     

Normal derivability in modal logic

The standard rule of necessitation in systems of natural deduction for the modal logic S4 concludes □A from A whenever all assumptions A depends on are modal formulas. This condition prevents the composability and normalization of derivations, and therefore modifications of the rule have been suggested. It is shown that both properties hold if, instead of changing the rule of necessitation, all elimination rules are formulated in the manner of disjunction elimination, i.e. with an arbitrary consequence. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)