Flexible toggles and symmetric invertible asynchronous elementary cellular automata

A sequential dynamical system (SDS) consists of a graph $G$ with vertices $v_1,\dots ,v_n$, a state set $A$, a collection of “vertex functions” ${\left\{f_{v_i}\right\}}_{i=1}^n$, and a permutation $\pi \in S_n$ that specifies how to compose these functions to yield the SDS map $[G,{\left\{f_{v_i}\right\}}_{i=1}^n,\pi ]:A^n\to A^n$. In this paper, we study symmetric invertible SDS defined over the cycle graph $C_n$ using the set of states ${\mathbb{F}}_2$. These are, in other words, asynchronous elementary cellular automata (ECA) defined using ECA rules 150 and 105. Each of these SDS defines a group action on the set ${\mathbb{F}}_2^n$ of $n$-bit binary vectors. Because the SDS maps are products of involutions, this relates to generalized toggle groups, which Striker recently introduced. In this paper, we further generalize the notion of a generalized toggle group to that of a flexible toggle group; the SDS maps we consider are examples of Coxeter elements of flexible toggle groups.Our main result is the complete classification of the dynamics of symmetric invertible SDS defined over cycle graphs using the set of states ${\mathbb{F}}_2$ and the identity update order $\pi =123?n$. More precisely, if $T$ denotes the SDS map of such an SDS, then we obtain an explicit formula for $\left|{\text{Per}}_r\left(T\right)\right|$, the number of periodic points of $T$ of period $r$, for every positive integer $r$. It turns out that if we fix $r$ and vary $n$ and $T$, then $\left|{\text{Per}}_r\left(T\right)\right|$ only takes at most three nonzero values.     

Effect of asynchronous updating on the stability of cellular automata

Although cellular automata (CAs) were conceptualized as utter discrete mathematical models in which the states of all their spatial entities are updated simultaneously at every consecutive time step, i.e. synchronously, various CA-based models that rely on so-called asynchronous update methods have been constructed in order to overcome the limitations that are tied up with the classical way of evolving CAs. So far, only a few researchers have addressed the consequences of this way of updating on the evolved spatio-temporal patterns, and the reachable stationary states. In this paper, we exploit Lyapunov exponents to determine to what extent the stability of the rules within a family of totalistic CAs is affected by the underlying update method. For that purpose, we derive an upper bound on the maximum Lyapunov exponent of asynchronously iterated CAs, and show its validity, after which we present a comparative study between the Lyapunov exponents obtained for five different update methods, namely one synchronous method and four well-established asynchronous methods. It is found that the stability of CAs is seriously affected if one of the latter methods is employed, whereas the discrepancies arising between the different asynchronous methods are far less pronounced and, finally, we discuss the repercussions of our findings on the development of CA-based models.     

Comparative analysis of asynchronous cellular automata in stochastic pharmaceutical modelling

In pharmaceutical modelling, cellular automata have been used as an established tool to represent molecular changes through discrete structural interactions. The data quality provided by such modelling is found suitable for the early drug design phase where flexibility is paramount. While both synchronous (CA) and asynchronous (ACA) types of automata have been used, analysis of their nature and comparative influence on model outputs is lacking. In this paper, we outline a representative probabilistic CA for modelling complex controlled drug formulations and investigate its transition from synchronous to asynchronous update algorithms. The key investigation points include quantification of model dynamics through three distinct scenarios, parallelisation performance and the ability to describe different release phenomena, namely erosion, diffusion and swelling. The choice of the appropriate update mechanism impacts the perceived realism of the simulation as well as the applicability of large-scale simulations.     

Injective linear cellular automata and sofic groups

Let V be a finite-dimensional vector space over a field and let G be a sofic group. We show that every injective linear cellular automaton τ: V ^G → V ^G is surjective. As an application, we obtain a new proof of the stable finiteness of group rings of sofic groups, a result previously established by G. Elek and A. Szabó using different methods.     

Parallel implementation of asynchronous cellular automata on a 32-core computer

An efficient way of how some parallel algorithms of asynchronous cellular automata simulation can be mapped onto the architecture of a modern 32-core computer (4×Intel Xeon X7560) is investigated. An example is a model of the CO+O = CO₂ reaction on the surface of palladium particles.     

Dynamics of discrete automata

This review deals with the theory and practice of discrete automata, especially with transition processes and hazardous races in such automata.Translated from Itogi Nauki i Tekhniki. Teoriya Veroyatnostei, Matematicheskaya Statistika, Teoreticheskaya Kibernetika, Vol. 14, pp. 81–122, 1977.     

Planigon tessellation cellular automata

Cellular automata (CA) do not find as wide a use in chemical complexity determined by a crystal structure as in homogeneous reacting systems. A reason for this is discussed, and a superposition of planigons and parallelogons or Wigner‐Seitz tessellations is suggested that is derived from a crystallographic plane and is capable of representing chemical complexity at a single crystal face in terms of CA. The interplay between growth and form of two‐dimensional negative crystals is discussed in these terms as a particular example. © 1999 John Wiley & Sons, Inc.     

Cohomology of permutative cellular automata

We examineU(d) valued cocycles for a ?²⁺ action generated by a mixing, permutative cellular automaton and show that the set of Hölder continuous cocycles (for a given Hölder order) which are cohomologous to constant cocycles is both open and closed in the appropriate topology. A continuous dimension function with values in {0, 1,…,d} is defined on cocycles; a cocycle is cohomologous to a constant precisely when the value isd. Whend=1 (the abelian case) the first (essential) cohomology group is countable. IfU(1)? circle is replaced by a finite subgroup, this cohomology group is finite.     

Reversibility of linear cellular automata

In this paper the reversibility problem for linear cellular automata defined by a characteristic matrix of the form of a pentadiagonal matrix is tackled. Specifically, a criterion for the reversibility in terms of the number of cells is stated and, in these cases, the inverse cellular automata are explicitly computed.     

Representation of automata by groups

We consider the problem of representing abstract automata by finite groups. We prove the universality of the proposed representation and study its properties.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 44, No. 10, pp. 1412–1416, October, 1992.     

Finite automata presentable abelian groups

We give new examples of FA presentable torsion-free abelian groups. Namely, for every n2, we construct a rank n indecomposable torsion-free abelian group which has an FA presentation. We also construct an FA presentation of the group in which every nontrivial cyclic subgroup is not FA recognizable.     

Prevalence of odometers in cellular automata

We consider left permutive cellular automata  with no memory and positive anticipation, defined on the space of all doubly infinite sequences with entries from a finite alphabet. For each such automaton that is not one-to-one, there is a dense set of points  such that is topologically conjugate to an odometer, the ``' map on the countable product of finite cyclic groups. This set is a dense subset of an appropriate subspace. We identify the odometer in several cases.

     

Mixing properties of one-dimensional cellular automata

We study a class of endomorphisms on the space of bi-infinite sequences over a finite set, and show that such a map is onto if and only if it is measure-preserving. A class of dynamical systems arising from these endomorphisms are strongly mixing, and some of them even -mixing. Some of these are isomorphic to the one-sided shift on in both the topological and measure-theoretical sense. Such dynamical systems can be associated to , the Cuntz-algebra of order , in a natural way.

     

Periodic orbits for additive cellular automata

We formulate and study a necessary and sufficient condition for a configuration of any type of infinite additive cellular automata to have periodic behavior in time. The number of orbits with periodn is counted. Relations between spatial and temporal periods are discussed.Supported in part by G.M.C.I., DEEE-LNETI (Portugal).     

Linear cellular automata with boundary conditions

The main results of the paper concern graphs of linear cellular automata with boundary conditions. We show that the connected components of such graphs are direct sums of trees and cycles, and we provide a complete characterization of the trees, as well as enumerate the cycles of various lengths. Our work generalizes and clarifies results obtained previously in special cases.     

Lyapunov exponents for one-dimensional cellular automata

Summary In the paper we give a mathematical definition of the left and right Lyapunov exponents for a one-dimensional cellular automaton (CA). We establish an inequality between the Lyapunov exponents and entropies (spatial and temporal).     

Asynchronous cellular automata and pattern classification

This article designs an efficient two‐class pattern classifier utilizing asynchronous cellular automata (ACAs). The two‐state three‐neighborhood one‐dimensional ACAs that converge to fixed points from arbitrary seeds are used here for pattern classification. To design the classifier, (1) we first identify a set of ACAs that always converge to fixed points from any seeds, (2) each ACA should have at least two but not huge number of fixed point attractors, and (3) the convergence time of these ACAs are not to be exponential. To address the second issue, we propose a graph, coined as fixed point graph of an ACA that facilitates in counting the fixed points. We further perform an experimental study to estimate the convergence time of ACAs, and find there are some convergent ACAs which demand exponential convergence time. Finally, we identify there are 73 (out of 256) ACAs which can be effective candidates as pattern classifier. We use each of the candidate ACAs on some standard datasets, and observe the effectiveness of each ACAs as pattern classifier. It is observed that the proposed classifier is very competitive and performs reliably better than many standard existing classifier algorithms. © 2016 Wiley Periodicals, Inc. Complexity 21: 370–386, 2016