Search

Many models of self-assembly have been shown to be capable of performing computation. Tile Automata was recently introduced combining features of both Cellular Automata and the 2-Handed Model of self-assembly both capable of universal computation. In this work we study the complexity of Tile Automata utilizing features inherited from the two models mentioned above. We first present a construction for simulating Turing machines that performs both covert and fuel efficient computation. We then explore the capabilities of limited Tile Automata systems such as 1-dimensional systems (all assemblies are of height 1) and freezing systems (tiles may not repeat states). Using these results we provide a connection between the problem of finding the largest uniquely producible assembly using n states and the busy beaver problem for non-freezing systems and provide a freezing system capable of uniquely assembling an assembly whose length is exponential in the number of states of the system. We finish by exploring the complexity of the Unique Assembly Verification problem in Tile Automata with different limitations such as freezing and systems without the power of detachment. [ABSTRACT FROM AUTHOR]

The use of Cellular Automata (CA) in combination with Learning Automata (LA) has demonstrated effectiveness in handling hard-to-be-solved problems. Due to their capacity to learn and adapt, as well as their inherent parallelism, they can expedite the problem-solving process for a range of problems, such as challenging logic puzzles. One such puzzle is Sudoku, which poses a combinatorial optimization challenge of great difficulty and complexity. In this study, a Sudoku puzzle was represented as an Irregular Learning Cellular Automaton (ILCA), using a reward and penalty algorithm to resolve it. Simulations for an amount of 400 puzzles were performed, while the results demonstrate that the proposed algorithm operates effectively, highlighting the concurrent and learning capabilities of the ILCA structure. Furthermore, two different performance enhancement methods are investigated, namely learning rates method and selective probability reset rule, which are able to increase the initial performance by 26.8 % and to achieve an overall 99.3 % resolution rate. [ABSTRACT FROM AUTHOR]

In this paper, we study how synchronization and state estimation are related in the context of elementary cellular automata. We first characterize the geometric properties of the synchronization error between two replicas of a 1D elementary cellular automata following Wolfram's rule 18. We propose a simple approach to statistically model the transient phase of the spreading of the synchronization error. We finally present a way to utilize our model of the error spreading to place mobile sensors in order to improve the overall replica synchronization in the case in which the initial error is small. [ABSTRACT FROM AUTHOR]

We consider the car following problem for a set of autonomous vehicles following each other on either an infinite or circular road. The behavior of each car is specified by its "speed regulator", a device that decides to increase or decrease the speed of the car as a function of the head-tail distance to its predecessor and the speed of both cars. A collective behavior emerges that corresponds to previously proposed cellular automata traffic models. We further analyze the traffic patterns of the system in the long term, as governed by the speed regulator and we study under which conditions traffic patterns of maximum flow can or cannot be reach. We show the existence of suboptimal flow conditions that require external coordination mechanisms (that we do not consider in this paper) in order to reach the optimal flow achievable with the given density. In contrast with other approaches, we do not try to reproduce observed or measured traffic patterns. We analyze a deterministic speed regulator in order to decipher the emergent dynamics, and to ponder what maneuvers can be safely performed. Here, we restrict our attention to the car following problem. By comparing our speed regulator with classical models, auch as the Nagel–Schreckenberg and KKW models, we observe that although our regulator is formulated in simple terms, its dynamics share similarities with these models. In particular, the KKW model is designed to reproduce the observed behavior that a trailing car in the synchronization range of the leading car tends to regulate its speed to maintain a constant distance. this same behavior is adopted by our speed regulator, showing that this is a safe way of driving. [ABSTRACT FROM AUTHOR]

The goal of this paper it to explore the possibility to simplify a stochastic complex dynamical system by reducing the number of its degrees of freedom, through a coarse graining procedure. Our objective is to create reduced systems which requires less computational burden to control. In other words, the question is whether one can act on the simplified system to control its evolution towards a given target, so that the same strategy also applies to the full system. We analyze this problem in three stages. First we consider the general case of coarse-graining 1D cellular automata. We show that the procedure is expected to produce extra stochasticity in the system, while still retaining some characteristics of the original system. In a second step, we study a 1D voter model for which the coarse-graining procedure requires component weighting, with weights based on causal paths. Finally, in a third part, we consider the same voter model on a scale-free graph, and perform a reduction according to a partition of the graph in communities. The equivalence between the reduced and full systems, whether controlled or not, is investigated through a delayed mutual information analysis, a concept from information theory. [ABSTRACT FROM AUTHOR]

A cellular automata model has been developed to study the sintering behavior of ceramic particles. In this model, the only physical rule that drives the evolution of the system is to reduce the energy at the interface between the mass cells and the void cells. The meaning of several computational parameters, such as particle size or computational temperature, were investigated. Experiments of partial sintering of spherical particles of silica were performed and it was verified that this model successfully mimics the neck formation. Moreover, other experimental evidences of the stages of the densification, such as the formation of the intermediate vermicular microstructure or the dependence of porosity with temperature, were also qualitatively simulated. [ABSTRACT FROM AUTHOR]

Cellular Automata have successfully been successfully applied to the modeling and simulation of pedestrian and crowd dynamics. In particular, the investigated scenarios have often been focused on the evaluation of medium–high population density situations, in which the motivation of pedestrians to reach a certain location overcomes their tendency to naturally respect proxemic distances. The global COVID-19 outbreak, though, has shown that sometimes it is crucial to contemplate how proxemic tendencies are emphasized and amplified by the affective state of the individuals involved in the scenario, representing an important factor to take into consideration when investigating the behaviour of a crowd. In this paper we present a research effort aimed at integrating results of quantitative analyses regarding the effects of affective states on the perception of distances maintained by different types of pedestrians with the modeling of pedestrian movement choices in a cellular automata framework. [ABSTRACT FROM AUTHOR]

Most of the approaches published in the literature to construct S-boxes via Cellular Automata (CA) work by either iterating a finite CA for several time steps, or by a one-shot application of the global rule. The main characteristic that brings together these works is that they employ a single CA rule to define the vectorial Boolean function of the S-box. In this work, we explore a different direction for the design of S-boxes that leverages on Orthogonal CA (OCA), i.e. pairs of CA rules giving rise to orthogonal Latin squares. The motivation stands on the facts that an OCA pair already defines a bijective transformation, and moreover the orthogonality property of the resulting Latin squares ensures a minimum amount of diffusion. We exhaustively enumerate all S-boxes generated by OCA pairs of diameter 4 ≤ d ≤ 6 , and measure their nonlinearity. Interestingly, we observe that for d = 4 and d = 5 all S-boxes are linear, despite the underlying CA local rules being nonlinear. The smallest nonlinear S-boxes emerges for d = 6 , but their nonlinearity is still too low to be used in practice. Nonetheless, we unearth an interesting structure of linear OCA S-boxes, proving that their Linear Components Space is itself the image of a linear CA, or equivalently a polynomial code. We finally classify all linear OCA S-boxes in terms of their generator polynomials. [ABSTRACT FROM AUTHOR]

Our long-term project involves performing general-purpose computation on 2D amorphous computing media, which consist of arbitrary many, small, identical processing elements that are homogeneously spread in 2D Euclidian space, and that communicate locally in space. While the minimal assumptions on hardware provide the fascinating perspective of arbitrary large computing power, they also make programming notoriously difficult. Furthermore, our project involves simulating objects extended in 2D-space, called "blobs". Maintaining the connectedness of blobs while they move in space adds another layer of difficulty since it demands to process the topology of 2D space. This paper describes a new parallel data structure that can simplify the programming task, in this context. In computer graphics, processing related to 2D topology is performed by using triangle meshes. We consider synchronous media whose underlying network is also a triangle mesh. Our data structure, derived from computer graphics, is anchored on that mesh so that its operations can be compiled on the medium. More precisely, our compiler produces a circuit of logic gates, which enables a high-performance simulation, in the case of crystalline media (Cellular Automata). We demonstrate the expressiveness of the data structure's operation by using an incremental and modular programming style. We program, first small, then larger building-block functions, and re-use them. Blobs are implemented and re-used to compute the Voronoï diagram. What is the scope of the data-structure? This poses the question of whether there exists a universal set of primitives able to program any processing specified only in terms of 2D-geometry. [ABSTRACT FROM AUTHOR]

This document is a preface to a special issue of the journal Natural Computing. The issue focuses on the topic of Cellular Automata (CA) and their applications in various scientific fields. The preface provides an overview of the International Conference on Cellular Automata for Research and Industry (ACRI), which serves as a platform for researchers to discuss current trends and challenges in the field. The special issue includes selected papers from the 15th ACRI conference, covering both theoretical and applied aspects of CA. The papers explore topics such as the generation of nonlinear substitution boxes for cryptography, system reduction in complex systems, synchronization of elementary cellular automata, solving Sudoku puzzles using learning cellular automata, modeling the sintering behavior of ceramics, modeling affective states in pedestrian simulations, and optimal safe driving dynamics for autonomous vehicles. The preface acknowledges the contributions of the authors, reviewers, and committees involved in the conference and publication process. [Extracted from the article]

We show that a cellular automaton on a one-dimensional two-sided mixing subshift of finite type is a von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto its image in the category of sofic shifts and block maps. It follows from previous joint work of the author and Törmä that von Neumann regularity is a decidable condition, and we decide it for all elementary CA, obtaining the optimal radii for weak generalized inverses. Two sufficient conditions for non-regularity are having a proper sofic image or having a point in the image with no preimage of the same period. We show that the non-regular ECA 9 and 28 cannot be proven non-regular using these methods. We also show that a random cellular automaton is non-regular with high probability. [ABSTRACT FROM AUTHOR]

In this paper, we formalize precisely the sense in which the application of a cellular automaton to partial configurations is a natural extension of its local transition function through the categorical notion of Kan extension. In fact, the two possible ways to do such an extension and the ingredients involved in their definition are related through Kan extensions in many ways. These relations provide additional links between computer science and category theory, and also give a new point of view on the famous Curtis–Hedlund theorem of cellular automata from the extended topological point of view provided by category theory. These links also allow to relatively easily generalize concepts pioneered by cellular automata to arbitrary kinds of possibly evolving spaces. No prior knowledge of category theory is assumed for the most part. [ABSTRACT FROM AUTHOR]

Cellular automata (CA) are an interesting computational model for designing pseudorandom number generators (PRNG), due to the complex dynamical behavior they can exhibit depending on the underlying local rule. Most of the CA-based PRNGs proposed in the literature, however, suffer from poor diffusion since a change in a single cell can propagate only within its neighborhood during a single time step. This might pose a problem especially when such PRNGs are used for cryptographic purposes. In this paper, we consider an alternative approach to generate pseudorandom sequences through orthogonal CA (OCA), which guarantees a better amount of diffusion. After defining the related PRNG, we perform an empirical investigation of the maximal cycles in OCA pairs up to diameter d = 8 . Next, we focus on OCA induced by linear rules, giving a characterization of their cycle structure based on the rational canonical form of the associated Sylvester matrix. Finally, we devise an algorithm to enumerate all linear OCA pairs characterized by a single maximal cycle, and apply it up to diameter d = 16 and d = 13 for OCA respectively over the binary and ternary alphabets. [ABSTRACT FROM AUTHOR]

The Besicovitch pseudometric is a shift-invariant pseudometric over the set of infinite sequences, that enjoys interesting properties and is suitable for studying the dynamics of cellular automata. It corresponds to the asymptotic behavior of the Hamming distance on longer and longer prefixes. Though dynamics of cellular automata were already studied in the literature, we propose the first study of the dynamics of substitutions. We characterize those that yield a well-defined dynamical system as essentially the uniform ones. We also explore a variant of this pseudometric, the Feldman–Katok pseudometric, where the Hamming distance is replaced by the Levenshtein distance. Like in the Besicovitch space, cellular automata are Lipschitz in this space, but here also all substitutions are Lipschitz. In both spaces, we discuss equicontinuity of these systems, give a number of examples, and generalize our results to the class of dill maps, that embeds both cellular automata and substitutions. [ABSTRACT FROM AUTHOR]

Little is known about the dynamics of k-ary (binary, ternary, quaternary, quinary, etc.) reversible number-conserving cellular automata. Here, we present some preliminary results in the case of seven states. In particular, we examine one of the most complex seven-state reversible and number-conserving rules and provide a full description of its dynamics. [ABSTRACT FROM AUTHOR]

We prove that the limit dynamics of any finite automata network under the parallel update schedule correspond exactly to the fixed points of a so-called strictly one-way cellular automaton. This correspondence is proven to be exact, as any strictly one-way cellular automaton can be transformed into a corresponding automata network, the limit dynamics of the latter corresponding exactly to the fixed points of the former. This transformation is operated using output functions, which have been developed in the author's previous works. [ABSTRACT FROM AUTHOR]

Gauge-invariance is a fundamental concept in Physics—known to provide mathematical justification for the fundamental forces. In this paper, we provide discrete counterparts to the main gauge theoretical concepts directly in terms of cellular automata. More precisely, the notions of gauge-invariance and gauge-equivalence in cellular automata are formalized. A step-by-step gauging procedure to enforce this symmetry upon a given cellular automaton is developed, and three examples of gauge-invariant cellular automata are examined. [ABSTRACT FROM AUTHOR]

In the context of the propagation of infectious diseases, when a sufficient degree of immunisation is achieved within a population, the spread of the disease is ended or significantly decreased, leading to collective immunity, meaning the indirect protection given by immune individuals to susceptible individuals. Here we describe the estimates of the collective immunity to COVID-19 from a stochastic cellular automaton based model designed to emulate the spread of SARS-CoV-2 in a population of static individuals interacting only via a Moore neighbourhood of radius one, with a view to analyze the impact of initially immune individuals on the dynamics of COVID-19. This impact was measured by comparing a progression of initial immunity ratio—the percentage of immunised individuals before patient zero starts infecting its neighbourhood—from 0 to 95% of the initial population, with the number of susceptible individuals not contaminated, the peak value of active cases, the total number of deaths and the emulated pandemic duration in days. The influence of this range of immunities over the model was tested with different parameterisations regarding the uncertainties involved in the model such as the durations of the cellular automaton states, the contamination contributions of each state and the state transition probabilities. A collective immunity threshold of 55 % ± 2.5 % on average was obtained from this procedure, under four distinct parameterisations, which is in tune with the estimates of the currently available medical literature, even increasing the uncertainty of the input parameters. [ABSTRACT FROM AUTHOR]

In this study, we introduce an application of a Cellular Automata (CA)-based system for monitoring and estimating the spread of epidemics in real world, considering the example of a Greek city. The proposed system combines cellular structure and graph representation to approach the connections among the area's parts more realistically. The original design of the model is attributed to a classical SIR (Susceptible–Infected–Recovered) mathematical model. Aiming to upgrade the application's effectiveness, we have enriched the model with parameters that advances its functionality to become self-adjusting and more efficient of approaching real situations. Thus, disease-related parameters have been introduced, while human interventions such as vaccination have been represented in algorithmic manner. The model incorporates actual geographical data (GIS, geographic information system) to upgrade its response. A methodology that allows the representation of any area with given population distribution and geographical data in a graph associated with the corresponding CA model for epidemic simulation has been developed. To validate the efficient operation of the proposed model and methodology of data display, the city of Eleftheroupoli, in Eastern Macedonia—Thrace, Greece, was selected as a testing platform (Eleftheroupoli, Kavala). Tests have been performed at both macroscopic and microscopic levels, and the results confirmed the successful operation of the system and verified the correctness of the proposed methodology. [ABSTRACT FROM AUTHOR]

The problem of an optimal coverage of a wireless sensor network area is considered. To solve this problem, a Cellular Automata (CA) approach is proposed. More specifically, the objective is to find CA rules which are able to cover the 2D space by a minimum number of so–called "Sensor Tiles". A sensor tile consists of a von Neumann neighborhood of range 2 centered at sensor "point" and surrounded by 12 sensing "pixels". Two probabilistic CA rules were designed that can perform this task. Results of an experimental study show that the first rule evolves very fast stable sub-optimal coverings, starting from a random configuration. The second rule finds optimal coverings, however it needs much more time for their evolution. The results are supported by a theoretical study on von Neumann neighborhoods and borrowing either from heuristics or from the spectral theory of circulant graphs. [ABSTRACT FROM AUTHOR]

To determine the computational capacity of cellular automata they are often investigated towards their ability to accept formal languages within certain time constraints. In this paper, we take up an opposite position and look at cellular automata towards their ability to generate patterns, within certain time constraints. As an example we describe a construction of a cellular automaton that generates prefixes of the Oldenburger–Kolakoski sequence within real time. Furthermore, we study the real-time generation of unary and non-unary patterns in depth. In the unary case, we obtain a characterization by time-constructible functions and their corresponding unary formal languages. In the non-unary case, we provide constructions that generate any arbitrary given properly thin context-free language as well as all prefixes of any given automatic sequence. [ABSTRACT FROM AUTHOR]

This tutorial is about cellular automata that exhibit cold dynamics. By this we mean zero Kolmogorov-Sinai entropy, stabilization of all orbits, trivial asymptotic dynamics, or similar properties. These are essentially transient and irreversible dynamics, but they capture many examples from the literature, ranging from crystal growth to epidemic propagation and symmetric majority vote. A collection of properties is presented and discussed: nilpotency and asymptotic, generic or mu- variants, unique ergodicity, convergence, bounded-changeness, freezingness. They all correspond to the cold dynamics paradigm at various degrees, and we study their links and differences by key examples and results. Besides dynamical considerations, we also focus on computational aspects: we show how such cold cellular automata can still compute under their dynamical constraints, and what are their computational limitations. The purpose of this tutorial is to illustrate how the richness and complexity of the model of cellular automata are preserved under such strong constraints. By putting forward some open questions, it is also an invitation to look more closely at this cold dynamics territory, which is far from being completely understood. [ABSTRACT FROM AUTHOR]

An interesting thread in the research of Boolean functions for cryptography and coding theory is the study of secondary constructions: given a known function with a good cryptographic profile, the aim is to extend it to a (usually larger) function possessing analogous properties. In this work, we continue the investigation of a secondary construction based on cellular automata (CA), focusing on the classes of bent and semi-bent functions. We prove that our construction preserves the algebraic degree of the local rule, and we narrow our attention to the subclass of quadratic functions, performing several experiments based on exhaustive combinatorial search and heuristic optimization through Evolutionary Strategies (ES). Finally, we classify the obtained results up to permutation equivalence, remarking that the number of equivalence classes that our CA-XOR construction can successfully extend grows very quickly with respect to the CA diameter. [ABSTRACT FROM AUTHOR]

We study two questions related to the abelian sandpile model, those questions are: can we predict the dynamics of sandpiles avalanches? Can we efficiently stop an evolving avalanche? We study the problem of deciding wether all the nodes of a sandpile grid will be toppled by an evolving avalanche. We identify an important subproblem of this prediction problem, namely: the problem of recognizing the recurrent configurations of the sandpile dynamics. This latter problem can be solved in linear time by simulating the appropriate sandpile avalanches. We ask: do there exist sequential algorithms that solve this recognition problem in sublinear time? We prove that there do not exist sublinear time sequential algorithms that solve this problem in a probabilistic approximately correct way. This means that those avalanches cannot be predicted by a sequential algorithm. We also study the problem of fighting against avalanches. This latter problem resembles the classical firefighter problem. We prove that fighting against two-dimensional avalanches is harder than fighting against fires on forests of low depth. [ABSTRACT FROM AUTHOR]

We study the computational capacity of self-verifying iterative arrays (SVIA ). A self-verifying device is a nondeterministic device whose nondeterminism is symmetric in the following sense. Each computation path can give one of the answers yes, no, or do not know. For every input word, at least one computation path must give either the answer yes or no, and the answers given must not be contradictory. It turns out that, for any time-computable time complexity, the family of languages accepted by SVIA s is a characterization of the so-called complementation kernel of nondeterministic iterative array languages, that is, languages accepted by such devices whose complementation is also accepted by such devices. SVIA s can be sped-up by any constant multiplicative factor as long as the result does not fall below realtime. We show that even realtime SVIA are as powerful as lineartime self-verifying cellular automata and vice versa. So they are strictly more powerful than the deterministic devices. Closure properties and various decidability problems are considered. [ABSTRACT FROM AUTHOR]

The expanding cellular automata (XCA) variant of cellular automata is investigated and characterized from a complexity-theoretical standpoint. An XCA is a one-dimensional cellular automaton which can dynamically create new cells between existing ones. The respective polynomial-time complexity class is shown to coincide with ≤ tt p (NP) , that is, the class of decision problems polynomial-time truth-table reducible to problems in NP . An alternative characterization based on a variant of non-deterministic Turing machines is also given. In addition, corollaries on select XCA variants are proven: XCAs with multiple accept and reject states are shown to be polynomial-time equivalent to the original XCA model. Finally, XCAs with alternative acceptance conditions are considered and classified in terms of ≤ tt p (NP) and the Turing machine polynomial-time class P . [ABSTRACT FROM AUTHOR]

Iterative arrays whose internal inter-cell communication is quantitatively restricted are investigated. The quantity of communication is measured by counting the number of uses of the links between cells. In particular, iterative arrays are studied where the maximum number of communications per cell occurring in accepting computations is drastically bounded by a constant number. Additionally, the iterative arrays have to work in realtime. We study the computational capacity of such devices. For example, a result is that a strict and dense hierarchy with respect to the constant number of communications exists. Due to their very restricted communication, the question arises whether the usually studied decidability problems such as, for example, emptiness, finiteness, inclusion, or equivalence become decidable for such devices. However, it can be shown that all such decidability questions remain undecidable even if only four communications per cell are allowed. Finally, the undecidability results are shown to hold as well for one-way and two-way cellular automata having at most four communications per cell. [ABSTRACT FROM AUTHOR]

For a group G and a finite set A, denote by End (A G) the monoid of all continuous shift commuting self-maps of A G and by Aut (A G) its group of units. We study the minimal cardinality of a generating set, known as the rank, of End (A G) and Aut (A G) . In the first part, when G is a finite group, we give upper and lower bounds for the rank of Aut (A G) in terms of the number of conjugacy classes of subgroups of G. In the second part, we apply our bounds to show that if G has an infinite descending chain of normal subgroups of finite index, then End (A G) is not finitely generated; such is the case for wide classes of infinite groups, such as infinite residually finite or infinite locally graded groups. [ABSTRACT FROM AUTHOR]

This document is a correction notice for an article titled "Cellular automata simulations of the sintering behavior of ceramics driven by surface energy reduction" published in the journal Natural Computing. The correction states that an incorrect figure appeared in the original article and provides the correct version of the figure. The correction notice also includes a statement from the publisher, Springer Nature, emphasizing their neutrality and impartiality. The authors of the article are listed as Garrido-Regife Laura, Jiménez-Morales Francisco, González-Sánchez Manuela, Rivero-Antúnez Pedro, and Morales-Flórez Víctor. [Extracted from the article]

A natural way to interpret a cellular automaton (CA) is as a mechanism that computes, in a distributed way, some function f. In other words, from a computer science point of view, CAs can be seen as distributed systems where the cells of the CAs are nodes of a network linked by communication channels. A classic measure of efficiency in such distributed systems is the number of bits exchanged during the computation process. A typical approach is to look for bottlenecks: channels through which the nature of the function f forces the exchange of a significant number of bits. In practice, a widely used way to understand such congestion phenomena is to partition the system into two subsystems and try to find bounds for the number of bits that must pass through the channels that join them. Finding these bounds is the focus of communication complexity theory. Measuring the communication complexity of some problems induced by a CA ϕ turned out to be tremendously useful to give clues regarding the intrinsic universality of ϕ (a CA is said to be intrinsically universal if it is capable of emulating any other). In fact, there exist particular problems P 's for which the following key property holds: if ϕ is intrinsically universal, then the communication complexity of P (ϕ) must be maximal. In this tutorial, we intend to explain the connections that were found, through a series of papers, between intrinsic universality and communication complexity in CAs. [ABSTRACT FROM AUTHOR]

We consider the problem of computing the Lyapunov exponents of reversible cellular automata (CA). We show that the class of reversible CA with right Lyapunov exponent 2 cannot be separated algorithmically from the class of reversible CA whose right Lyapunov exponents are at most 2 - δ for some absolute constant δ > 0 . Therefore there is no algorithm that, given as an input a description of an arbitrary reversible CA F and a positive rational number ϵ > 0 , outputs the Lyapunov exponents of F with accuracy ϵ . We also compute the average Lyapunov exponents (with respect to the uniform measure) of the reversible CA that perform multiplication by p in base pq for coprime p , q > 1 . [ABSTRACT FROM AUTHOR]

For any mixing SFT X we construct a reversible shift-commuting continuous map (automorphism) which breaks any given finite point of the subshift into a finite collection of gliders traveling into opposing directions. As an application we prove a finitary Ryan's theorem: the automorphism group Aut (X) contains a two-element subset S whose centralizer consists only of shift maps. We also give an example which shows that a stronger finitary variant of Ryan's theorem does not hold even for the binary full shift. [ABSTRACT FROM AUTHOR]

Iterative arrays with restricted internal inter-cell communication are investigated. A quantitative measure for the communication is defined by counting the number of uses of the links between cells and it is differentiated between the sum of all communications of an accepting computation and the maximum number of communications per cell occurring in accepting computations. The computational complexity of both classes of devices is investigated and put into relation. In addition, a strict hierarchy depending on the maximum number of communications per cell is established. Furthermore, it is shown that almost all commonly studied decidability questions are not semidecidable for iterative arrays with restricted communication. Finally, non-recursive trade-offs are proved among the iterative arrays providing the strict hierarchy depending on the maximum number of communications per cell. [ABSTRACT FROM AUTHOR]

We study the problem of sequentializing a cellular automaton without introducing any intermediate states, and only performing reversible permutations on the tape. We give a decidable characterization of cellular automata which can be written as a single sweep of a bijective rule from left to right over an infinite tape. Such cellular automata are necessarily left-closing, and they move at least as much information to the left as they move information to the right. [ABSTRACT FROM AUTHOR]

We introduce and explore a type of discrete dynamic system inheriting some properties of both cellular automata (CA) and L-systems. Originally suggested by Jean Della Dora, and thus called DEM-systems after him and the two current authors, these systems can have the structural flexibility of an L-system as well as algebraic properties of CA. They are defined as sequences on a one-dimensional loop with rules governing dynamics in which new sites can be created, depending on the states of a neighbourhood of sites, and complex behaviour can be generated. Although the definition of DEM-systems is quite broad, we define some subclasses, for which more complete results can be obtained. For example, we define an additive subclass, for which algebraic results on asymptotic growth are possible, and an elementary class of particularly simple rules, for which nevertheless impressive complexity is achievable. Unlike for CA, finite initial sequences can produce positive spatial entropy over time. However, even in cases where the entropy is zero, considerable complexity is possible, especially when the sequence length grows to infinity, and we demonstrate and study behaviours of DEM-systems including fragmentation of sequences, self-reproducing patterns, self-similar but irregular patterns, patterns that not only produce new sites but produce producers of new sites, and sequences whose growth rate is sublinear, linear, quadratic, cubic, or exponential. The most complex behaviour from small finite initial conditions and the simplest class of rules appear to have positive entropy, a suggestion for which we have so far only stong numerical evidence, though we present a proof for these 'elementary' DEM-systems that entropy cannot reach the theoretical maximum of 1. [ABSTRACT FROM AUTHOR]

We continue the study of asynchrony immunity in cellular automata (CA), which can be considered as a generalization of correlation immunity in the case of vectorial Boolean functions. The property could have applications as a countermeasure for side-channel attacks in CA-based cryptographic primitives, such as S-boxes and pseudorandom number generators. We first give some theoretical results on the properties that a CA rule must satisfy in order to meet asynchrony immunity, like central permutivity. Next, we perform an exhaustive search of all asynchrony immune CA rules of neighborhood size up to 5, leveraging on the discovered theoretical properties to greatly reduce the size of the search space. [ABSTRACT FROM AUTHOR]

We present an analysis of an additive cellular automaton (CA) under asynchronous dynamics. The asynchronous scheme is maxmin- ω , a deterministic system, introduced in our previous work with a binary alphabet. Extending this work, we study the impact of a larger alphabet, which also allows a meaningful inference of the behaviour of the resultant CA from the asymptotic behaviour of the maxmin- ω update system. Far from being a straightforward positive correlation between complexity and alphabet size, we show that there is a region of ω and alphabet size where complexity of CA is maximal. Thus, despite employing a fixed CA rule, the complexity of this CA can be controlled by ω and alphabet size. The main message is that the effect of maxmin- ω updating on the state of a network can be well understood, especially if the state alphabet is counter-intuitively large. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We present a panorama of the convergence properties of the 256 Elementary Cellular Automata under fully asynchronous updating, that is, when only one cell is updated at each time step. We regroup here various results which have been presented in different articles and expose a full analysis of the behaviour of finite systems with periodic boundary conditions. Our classification relies on the scaling properties of the average convergence time to a fixed point. We observe that different scaling laws can be found, which fall in one of the following classes: logarithmic, linear, quadratic, exponential and non-converging. The techniques for quantifying this behaviour rely mainly on Markov chain theory and martingales. Most behaviours can be studied analytically but there are still many rules for which obtaining a formal characterisation of their convergence properties is still an open problem. [ABSTRACT FROM AUTHOR]

Causal Graph Dynamics extend Cellular Automata to arbitrary time-varying graphs of bounded degree. The whole graph evolves in discrete time steps, and this global evolution is required to have a number of symmetries: shift-invariance (it acts everywhere the same) and causality (information has a bounded speed of propagation). We add a further physics-like symmetry, namely reversibility. In particular, we extend two fundamental results on reversible cellular automata, by proving that the inverse of a causal graph dynamics is a causal graph dynamics, and that these reversible causal graph dynamics can be represented as finite-depth circuits of local reversible gates. We also show that reversible causal graph dynamics preserve the size of all but a finite number of graphs. [ABSTRACT FROM AUTHOR]

This work is a thoughtful extension of the ideas sketched in Montalva et al. (AUTOMATA 2017 exploratory papers proceedings, 2017), aiming at classifying elementary cellular automata (ECA) according to their maximal one-step sensitivity to changes in the schedule of cells update. It provides a complete classification of the ECA rule space for all period sizes n > 9 and, together with the classification for all period sizes n ≤ 9 presented in Montalva et al. (Chaos Solitons Fractals 113:209–220, 2018), closes this problem and opens further questionings. Most of the 256 ECA rule's sensitivity is proved or disproved to be maximum thanks to an automatic application of basic methods. We formalize meticulous case disjunctions that lead to the results, and patch failing cases for some rules with simple arguments. This gives new insights on the dynamics of ECA rules depending on the proof method employed, as for the last rules 45 and 105 requiring (0011) ∗ induction patterns. [ABSTRACT FROM AUTHOR]

Roughly speaking, cellular automata and automata networks are discrete models based on the principles of interaction and locality essential to the vision of computation dear to Turing. Cellular automata as well as automata networks were introduced in the 1940s at the time of the basic developments of modern computer science. The contribution by Ville Salo studies von Neumann regularity, a notion of weak inverse in semi-groups, for cellular automata on mixing subshifts of finite type. [Extracted from the article]

In this paper we present an algorithm to track the motion of a salient object using Cellular Automata (CA). The overall work, taking inspiration from recent research on insect sensory motor system, investigates the application of non conventional computer vision approaches to evaluate their effectiveness in fulfilling this task. The proposed system employs the Sobel operator to individual frames, performing further elaborations through a CA, with the aim of detecting and characterizing moving entities within the field of view to support collision avoidance from the perspective of the viewer. The paper formally describes the adopted approach as well as its experimentation videos representing plausible situations. [ABSTRACT FROM AUTHOR]

The firing squad synchronization problem (FSSP, for short) on cellular automata has been studied extensively for more than fifty years, and a rich variety of FSSP algorithms has been proposed. Here we study the classical FSSP on a model of fault-tolerant cellular automata that might have possibly some defective cells and present the first state-efficient implementations of fault-tolerant FSSP algorithms for one-dimensional (1D) and two-dimensional (2D) cellular arrays. It is shown that, under some constraints on the length and distribution of defective cells, any 1D cellular array of length n with p defective cell segments can be synchronized in 2 n - 2 + p steps and the algorithm is realized on a 1D cellular automaton of length n , 2 ≤ n ≤ 50 , having 164 states and 4792 transition rules. In addition, we give by far a smaller-state implementation of a 2D FSSP algorithm that can synchronize any 2D rectangular array of size m × n , possibly including at most O(mn) isolated defective zones, exactly in 2 (m + n) - 4 steps on a cellular automaton with only 6 states and 935 transition rules. [ABSTRACT FROM AUTHOR]

Probabilistic cellular automata are extended stochastic systems, widely used for modelling phenomena in many disciplines. The possibility of controlling their behaviour is therefore an important topic. We shall present here an approach to the problem of controlling such systems by acting only on the boundary of a target region. In particular we are interested in optimal control, which is rather demanding in computational terms, so we present also a less demanding suboptimal method. Finally, we present an example of optimal control with avoidance. [ABSTRACT FROM AUTHOR]

Quantum cellular automata are arrays of identical finite-dimensional quantum systems, evolving in discrete-time steps by iterating a unitary operator G. Moreover the global evolution G is required to be causal (it propagates information at a bounded speed) and translation-invariant (it acts everywhere the same). Quantum cellular automata provide a model/architecture for distributed quantum computation. More generally, they encompass most of discrete-space discrete-time quantum theory. We give an overview of their theory, with particular focus on structure results; computability and universality results; and quantum simulation results. [ABSTRACT FROM AUTHOR]

Self-reconfigurable robots are built by modules which can move in relationship to each other, which allows the robot to change its physical form. Finding a sequence of module moves that reconfigures the robot from the initial configuration to the goal configuration is a hard task and many control algorithms have been proposed. In this paper, we present a novel method which combines a cluster-flow locomotion based on cellular automata together with a decentralized local representation of the spatial geometry based on membrane computing ideas. This new approach has been tested with computer simulations and real-world experiments performed with modular self-reconfigurable robots and represents a new point of view with respect other control methods found in the literature. [ABSTRACT FROM AUTHOR]

In the global synchronisation problem, one is asked to find a cellular automaton which has the property that every initial condition evolves into a homogeneous blinking state. We study this simple inverse problem for the case of one-dimensional systems with periodic boundary conditions. Two paradoxical observations are made: (a) despite the apparent simplicity of finding rules with good statistical results, there exist no perfect deterministic solutions to this problem, (b) if we allow the use of randomness in the local rule, constructing "perfect" stochastic solutions is easy. For the stochastic case, we give some rules for which the mean time of synchronisation varies quadratically with the number of cells and ask if this result can be improved. To explore more deeply the deterministic rules, we code our problem as a SAT problem and use SAT solvers to find rules that synchronise a large set of initial conditions (in appendix). [ABSTRACT FROM AUTHOR]

We introduce cellular automata whose cell spaces are left-homogeneous spaces, show that their global transition functions are closed under composition, prove a uniform as well as a topological variant of the Curtis–Hedlund–Lyndon theorem, and deduce that such an automaton is invertible if and only if its global transition function is bijective. Examples of left-homogeneous spaces are spheres, Euclidean spaces, as well as hyperbolic spaces acted on by isometries; uniform tilings acted on by symmetries; vertex-transitive graphs, in particular, Cayley graphs, acted on by automorphisms; groups acting on themselves by multiplication; and integer lattices acted on by translations. [ABSTRACT FROM AUTHOR]

We study a simple triangular partitioned cellular automaton (TPCA), and clarify its complex behavior. It is a CA with triangular cells, each of which is divided into three parts. The next state of a cell is determined by the three adjacent parts of its neighbor cells. This framework makes it easy to design reversible triangular CAs. Among them, isotropic and eight-state (i.e., each part has only two states) TPCAs are called elementary TPCAs (ETPCAs). They are extremely simple, since each of their local transition functions is described by only four local rules. In this paper, we investigate a specific reversible ETPCA T 0347 , where 0347 is its identification number in the class of 256 ETPCAs. In spite of the simplicity of the local function and the constraint of reversibility, evolutions of configurations in T 0347 have very rich varieties. It is shown that a glider, which is a space-moving pattern, and glider guns exist in this cellular space We also show that the trajectory and the timing of a glider can be fully controlled by appropriately placing stable patterns called blocks. Furthermore, using gliders to represent signals, we can implement universal reversible logic gates in it. By this, computational universality of T 0347 is derived. [ABSTRACT FROM AUTHOR]