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).     

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     

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.     

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.

     

COMPLEXITY ANALYSIS OF TIME SERIES GENERATED BY ELEMENTARY CELLULAR AUTOMATA

§1Introduction Fromthepointofviewofdynamicalsystemsthecellularautomata(CAs)canbeseen asaclassofinfinitedimensionaldynamicalsystems.OneofthefeaturesofCAsisthatby usingverysimplemappingruleitispossibletoobtainverycomplicatedspatio-temporal patterns.However,itstilllackseffectivemathematicalmethodstosolvetheclassification problemforCAs,ifnotconsideringtheextensivecomputerexperimentasin[1,2].Most finelyestablishedrigorousmethodsarerathercoarseandoftendifficulttobeusedin complexityanalysisfornon…     

Exact enumeration of acyclic deterministic automata

A linear recurrence relation is derived for the number of unlabelled initially connected acyclic automata. The coefficients of this relation are determined by another, alternating, recurrence relation. The latter determines, in particular, the number of acyclic automata with labelled states. Certain simple enumerative techniques developed by the author for counting initially connected automata and acyclic digraphs are combined and applied. Calculations show that the results obtained in this paper improve recent upper bounds for the number of minimal deterministic automata (with accepting states) recognizing finite languages. Various related questions are also discussed.     

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.     

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.     

Integrals, partitions, and cellular automata

We prove that

where is the decreasing function that satisfies , for . When is an integer and we deduce several combinatorial results. These include an asymptotic formula for the number of integer partitions not having consecutive parts, and a formula for the metastability thresholds of a class of threshold growth cellular automaton models related to bootstrap percolation.

     

Design of fast one-pass authenticated and randomized encryption schema using reversible cellular automata

A novel way to provide fast authenticated and randomized encryption is proposed using reversible cellular automata for the first time. A block-based cryptosystem is presented and shown to provide security against both active and passive attackers by the way of a strong authentication mechanism. The proposed system is much faster than existing authenticated encryption standards since only one pass per block is performed to ensure both encryption and integrity. Experimental results show robustness of the cryptosystem against several cryptanalysis techniques, when a formal proof of strict integrity preserving is included. Obtained results demonstrate superiority of the approach in both security and rapidity aspects.     

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.     

22号初等元胞自动机的极限语言复杂性

§1Introduction Thetaskofthispaperistosolvetheproblemproposedin[1],i.e.,toexplorethe complexityoflimitset,orequivalently,limitlanguageoftheelementarycellularautomaton ofrule22bythetoolsofformallanguagetheory.Cellularautomata(abbreviatedasCA),asmathematicalmodelsforcomplexnatural systemscontaininglargenumbersofsimpleidenticalcomponentswithlocalinteractions,havebeenwidelyusedinphysical,biological,chemicalandcomputationalsystems[2].Despitetheirsimpleconstruction,someCAcandisplayveryrichandcompl…     

Prevalence and structure of adding machines for cellular automata

Consider the collection of left permutive cellular automata Φ with no memory, defined on the space S of all doubly infinite sequences from a finite alphabet. There exists , a dense subset of S, such that is topologically conjugate to an odometer for all so long as Φm is not the identity map for any m. Moreover, Φ generates the same odometer for all . The set is a dense Gδ subset with full measure of a particular subspace of S.     

Reversible cellular automata with memory of delay type

The effect of delay type memory of past states on reversible elementary cellular automata (CA) is examined in this study. It is assessed in simple scenarios, such as elementary CA, but the feasibility of enriching the dynamics with memory in a general reversible CA context is also outlined. © 2014 Wiley Periodicals, Inc. Complexity 20: 49–56, 2014     

An algorithm for testing permutativeness of cellular automata

An effective procedure for deciding permutativeness of one-directional cellular automata on the one-sided full shift is presented. It is then implemented in C++, and used to test permutativeness of elementary cellular automata (those of radius 3).     

Some applications of propositional logic to cellular automata

In this paper we give a new proof of Richardson's theorem [31]: a global function G_?? of a cellular automaton ?? is injective if and only if the inverse of G_?? is a global function of a cellular automaton. Moreover, we show a way how to construct the inverse cellular automaton using the method of feasible interpolation from [20]. We also solve two problems regarding complexity of cellular automata formulated by Durand [12] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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     

Operads,quasiorders, and regular languages

We generalize the construction of multi-tildes in the aim to provide double multi-tilde operators for regular languages. We show that the underlying algebraic structure involves the action of some operads. An operad is an algebraic structure that mimics the composition of the functions. The involved operads are described in terms of combinatorial objects. These operads are obtained from more primitive objects, namely precompositions, whose algebraic counter-parts are investigated. One of these operads acts faithfully on languages in the sense that two different operators act in two different ways.     

Discontinuous cellular automaton method for crack growth analysis without remeshing

A numerical technical of discontinuous cellular automaton method for crack growth analysis without remeshing is developed. In this method, the level set method is employed to track the crack location and its growth path, where the level set functions and calculation grids are independent, so no explicit meshing for crack surface and no remeshing for crack growth are needed. Then, the discontinuous enrichment shape functions which are enriched by the Heaviside function and the exact near-tip asymptotic field functions are constructed to model the discontinuity of cracks. Finally, a discontinuous cellular automaton theory is proposed, which are composed of cell, neighborhood and updating rules for discontinuous case. There is an advantage that the calculation is only applied on local cell, so no assembled stiffness matrix but only cell stiffness is needed, which can overcome the stiffness matrix assembling difficulty caused by unequal degrees of nodal freedom for different cells, and much easier to consider the local properties of cells. Besides, the present method requires much less computer memory than that of XFEM because of it local property.     

Minimal reversible nonsymmetric rings

Marks showed that ${\mathbb{F}}_2{Q}_8$, the ${\mathbb{F}}_2$ group algebra over the quaternion group, is a reversible nonsymmetric ring, then questioned whether or not this ring is minimal with respect to cardinality. In this work, it is shown that the cardinality of a minimal reversible nonsymmetric ring is indeed 256. Furthermore, it is shown that although ${\mathbb{F}}_2{Q}_8$ is a duo ring, there are also examples of minimal reversible nonsymmetric rings which are nonduo.