Full papers | Exploratory papers

# Full papers

##### Alonso Castillo-Ramirez and Maximilien Gadouleau

Von Neumann Regular Cellular Automata

For any group G and any set A, a cellular automaton (CA) is a transformation of the configuration space A G defined via a finite memory set and a local function. Let CA(G; A) be the monoid of all CA over A G . In this paper, we investigate a generalisation of the inverse of a CA from the semigroup-theoretic perspective. An element τ ∈ CA(G; A) is von Neumann regular (or simply regular) if there exists σ ∈ CA(G; A) such that τ ◦ σ ◦ τ = τ and σ ◦ τ ◦ σ = σ, where ◦ is the composition of functions. Such an element σ is called a generalised inverse of τ . The monoid CA(G; A) itself is regular if all its elements are regular. We establish that CA(G; A) is regular if and only if |G| = 1 or |A| = 1, and we characterise all regular elements in CA(G; A) when G and A are both finite. Furthermore, we study regular linear CA when A = V is a vector space over a field F; in particular, we show that every regular linear CA is invertible when G is torsion-free (e.g. when G = Zᵈ , d ≥ 1), and that every linear CA is regular when V is finite-dimensional and G is locally finite with char(F) o(g) for all g ∈ G.

**Eric Goles, Diego Maldonado, Pedro Montealegre, Nicolas Ollinger**

On the computational complexity of the freezing non-strict majority automata

Consider a two dimensional lattice with the von Neumann neighborhood such that each site has a value belonging to {0, 1} which changes state following a freezing non-strict majority rule, i.e., sites at state 1 remain unchanged and those at 0 change iff two or more of it neighbors are at state 1. We study the complexity of the decision problem consisting in to decide whether an arbitrary site initially in state 0 will change to state 1. We show that the problem in the class NC proving a characterization of the maximal sets of stable sites as the tri-connected components.

##### Tatsuya Yamashita, Teijiro Isokawa, Ferdinand Peper, Ibuki Kawamata, Masami Hagiya

Turing-Completeness of Asynchronous Non-Camouflage Cellular Automata

Asynchronous Boolean totalistic cellular automata have recently attracted attention as promising models for the implementation of reaction-diffusion systems. It is unknown, however, to what extent they are able to conduct computation. In this paper, we introduce the so-called non-camouflage property, which means that a cell’s update is insensitive to neighboring states that equal its own state. This property is stronger than the Boolean totalistic property, which signifies the existence of states in a cell’s neighborhood, but is not concerned with how many cells are in those states. We argue that the non-camouflage property is extremely useful for the implementation of reaction-diffusion systems, and we construct an asynchronous cellular automaton with this property that is Turing-complete. This indicates the feasibility of computation by reaction-diffusion systems.

##### Véronique Terrier

Some computational limits of trellis automata

We investigate some computational limits of trellis automata. Reusing a counting argument introduced in [4], we show that: {x₁…xₙy₁…yₙ : xᵢyᵢ ∈ {ab, ba, bb} for i = 1, …, n} is not a trellis language.

**Sylvain Contassot-Vivier, Jean-François Couchot**

Canonical form of Gray Codes in N-cubes

In previous works, the idea of walking into a N-cube where a balanced Hamiltonian cycle have been removed has been proposed as the basis of a chaotic PRNG whose chaotic behavior has been proven. However, the construction and selection of the most suited balanced Hamiltonian cycles implies practical and theoretical issues. We propose in this paper a canonical form for representing isomorphic Gray codes. It provides a drastic complexity reduction of the exploration of all the Hamiltonian cycles and we discuss some criteria for the selection of the most suited cycles for use in our chaotic PRNG.

**Antonio Bernini**

Restricted Binary Strings and Generalized Fibonacci Numbers

We provide some interesting relations involving k-generalized Fibonacci numbers between the set F_n⁽ᵏ⁾ of length n binary strings avoiding k of consecutive 0’s and the set of length n strings avoiding k + 1 consecutive 0’s and 1’s with some more restriction on the first and last letter, via a simple bijection. In the special case k = 2 a probably new interpretation of Fibonacci numbers is given. Moreover, we describe in a combinatorial way the relation between the strings of F_n⁽ᵏ⁾ with an odd numbers of 1’s and the ones with an even number of 1’s.

**Nazim Fatès**

Diploid cellular automata: first experiments on the random mixtures of two elementary rules

We study a small part of the 8088 diploid cellular automata. These rules are obtained with a random mixture of two deterministic Elementary Cellular Automata. We use numerical simulations to study the mixtures obtained with three blind rules: the null rule, the identity rule and the inversion rule. As the mathematical analysis of such systems is a difficult task, we use numerical simulations to get insights into the dynamics of this class of stochastic cellular automata. We are particularly interested in studying phase transitions and various types of symmetry breaking.

**Pierre Guillon, Ville Salo**

Distortion in one-head machines and cellular automata

We give two families of examples of automorphisms of subshifts that are range-distorted, that is, the radius of their iterations grows sublinearly. One of these families comes from one-head machines, and allows us to build such automorphisms for the full shift, and to obtain undecidability results. We also give some conditions on the functions that can occur as such growths.

**Marcella Anselmo, Dora Giammarresi, Maria Madonia**

Infinite Two-dimensional Strong Prefix Codes: characterization and properties

A two-dimensional code is defined as a set X⊆Σ⁺⁺ of rectangular pictures over an alphabet Σ such that any picture over Σ is tilable in at most one way with pictures in X. It is in general undecidable whether a set of pictures is a code, even in the finite case. Recently, finite strong prefix codes were introduced in [3] as a family of decidable picture codes. In this paper we study infinite strong prefix codes and give a characterization for the maximal ones based on iterated extensions. Moreover, we prove some properties regarding the measure of these codes.

**Pietro Di Lena**

Equicontinuity and Sensitivity of Nondeterministic Cellular Automata

Nondeterministic Cellular Automata (NCA) are the class of multivalued functions characterized by nondeterministic block maps. We extend the notions of equicontinuity and sensitivity to multivalued functions and investigate the characteristics of equicontinuous, almost equicontinuous and sensitive NCA. The dynamical behavior of nondeterministic CA in these classes is much less constrained than in the deterministic setting. In particular, we show that there are transitive NCA with equicontinuous points and equicontinuous NCA that are not reversible.

**Martin Kutrib, Andreas Malcher and Matthias Wendlandt**

Fast One-Way Cellular Automata with Reversible Mealy Cells

We investigate cellular automata that are composed of reversible components with regard to the recognition of formal languages. In particular, real-time one-way cellular automata (OCA) are considered which are composed of reversible Mealy automata. Moreover, we differentiate between three notions of reversibility in the Mealy automata, namely, between weak and strong reversibility as well as reversible partitioned OCA which have been introduced by Morita in [14]. Here, it turns out that every real-time OCA can be transformed into an equivalent real-time OCA with weakly reversible automata in its cells, whereas the remaining two notions seem to be weaker. However, a non-semilinear language is provided that can be accepted by a real-time OCA with strongly reversible cells. On the other hand, we present a context-free, non-regular language that is accepted by some real-time reversible partitioned OCA.

**Gaétan Richard**

Filling curves constructed in cellular automata with aperiodic tiling

In many constructions on cellular automata, information is transmitted with signals propagating through a defined background. In this paper, we investigate the possibility of using aperiodic tiling inside zones delimited by signals. More precisely, we study curves delineated by CA-constructible functions and prove that most of them can be filled with the NW-deterministic tile set defined by Kari [1]. The achieved results also hint a new possible way to study deterministic tile sets.

**Lapo Cioni and Luca Ferrari**

Enumerative Results on the Schröder Pattern Poset

The set of Schröder words (Schröder language) is endowed with a natural partial order, which can be conveniently described by interpreting Schröder words as lattice paths. The resulting poset is called the Schröder pattern poset. We find closed formulas for the number of Schröder words covering/covered by a given Schröder word in terms of classical parameters of the associated Schröder path. We also enumerate several classes of Schröder avoiding words (with respect to the length),

i.e. sets of Schröder words which do not contain a given Schröder word.

**Luca Mariot, Enrico Formenti, Alberto Leporati**

Enumerating Orthogonal Latin Squares Generated by Bipermutive Cellular Automata

We consider the problem of enumerating pairs of bipermutive cellular automata (CA) which generate orthogonal Latin squares. Since the problem has already been settled for bipermutive CA with linear local rules, we address the general case of nonlinear rules, which could be interesting for cryptographic applications such as the design of cheater-immune secret sharing schemes. We first prove that two bipermutive CA generating orthogonal Latin squares must have pairwise balanced local rules. Then, we count the number of pairwise balanced bipermutive Boolean functions and enumerate those which generate orthogonal Latin squares up to n = 6 variables, classifying them with respect to their nonlinearity values.

# Exploratory papers

** Kenichi Morita**

Making reversible Turing machines in a reversible elementary triangular partitioned cellular automaton

Elementary triangular partitioned cellular automata (ETP-CAs) are one of the simplest subclasses of two-dimensional CAs. Among them, ETPCA 0347, where 0347 is an identification number in this class, is a reversible one that shows complex behavior. It is known that universal reversible logic gates are implemented in it. In this paper, however, instead of reversible gates, we use a particular reversible logic element with memory having an identification number 4-31 (RLEM 4-31). Here, we show RLEM 4-31 is directly implemented in ETPCA 0347. By this, we can compose a configuration of ETPCA 0347 that simulates a given reversible Turing machine very easily.

**Johan Kopra**

Universal Pattern Generation from Aperiodic Configurations

We study one-dimensional cellular automata Gp,q which multiply numbers by p in base pq for multiplicatively independent p and q. We show that for any t ∈ N+ the automaton Gtp,q generates all finite patterns over the pq-ary alphabet when it is given any aperiodic configuration as initial input.

**Joonatan Jalonen and Jarkko Kari**

Conjugacy of one-dimensional cellular automata is undecidable

Two cellular automata are strongly conjugate if there exists a shift-commuting conjugacy between them. We prove that the following two sets of pairs of one-dimensional cellular automata over a full shift are recursively inseparable: (i) pairs where one cellular automaton has strictly higher topological entropy than the other, and (ii) pairs that are strongly conjugate and both have zero topological entropy. Because there is no factor map from a lower entropy system to a higher entropy one, and there is no embedding of a higher entropy system into a lower entropy system, we immediately get as corollaries that the following decision problems are undecidable: Given two cellular automata F and G over a full shift: Are F and G conjugate? Is F a factor of G? Is F a subsystem of G? All of these are undecidable in both strong and weak variants (whether the homomorphism is required to commute with the shift or not, respectively) over two- and one-sided full shifts.

**Katsunobu Imai, Kyosuke Oroji and Tomohiro Kubota**

On weak universality of three-dimensional Larger than Life cellular automaton

This article is an exploratory report related to Larger than Life (LtL). LtL is a class of cellular automata and it can be regarded as a generalization of the game of Life. We show a radius-4 LtL rule is a candidate for weakly universal one.

**Rolf Hoffmann**

Algorithms of Cellular Automata Agents Forming a Checkerboard Pattern

Considered is a multi-agent system with agents, modeled by Cellular Automata. The agents have the task to form a checkerboard (CB) pattern on an n×n square field. The objective is to find the behavior (an algorithm) for the agents (realized by a finite state machine FSM), which can solve this task. The target pattern class can be described by local matching patterns (3 × 3 templates). The degree of order is the number of template hits. Our goal is to find perfect CB patterns with a maximum degree of order. Firstly, a single-agent algorithm G1 with four states is designed, where the agent starts in a corner. The agent walks on a shortest path, but needs some additional steps to turn to a free direction when sensing a border. Secondly, FSM algorithms for multiagent systems are evolved by a Genetic Algorithm for a 8 × 8 field. Now the agents can start at any random position. The evolved single-agent FSM algorithm uses another strategy than G1, a spiral-like trajectory. The fully packed system with 64 agents is the fastest, but it is also the most costly one, in terms of the (time-steps × number of agents) product.

**Hiroshi Umeo**

A Quest for the Smallest Partial FSSP Solutions — Recent Developments —

The synchronization in cellular automata has been known as the firing squad synchronization problem (FSSP) since its development, where the FSSP gives a finite-state protocol for synchronizing a large scale of cellular automata. A quest for smaller state FSSP solutions has been an interesting problem for a long time. Umeo, Kamikawa and Yunès [2009] answered partially by introducing a concept of partial FSSP solutions and proposing a full list of the smallest four-state symmetric powers-of-two FSSP protocols that can synchronize any one-dimensional (1D) ring cellular automata of length n = 2**^**k for any positive integer k ≥ 1. Afterwards, Ng [2011] also added a list of asymmetric FSSP partial solutions, thus completing the four-state powers-of-two FSSP partial solutions. The number f our is the smallest one in the class of FSSP protocols proposed so far. A question remained is that ”are there any other four-state partial solutions?”. In this paper, we answer to the question by proposing a new class of the smallest four-state FSSP protocols that can synchronize any 1D ring of length n = 2^k − 1 for any positive integer k ≥ 2. We show that the class includes a rich variety of FSSP protocols that consists of 39 symmetric solutions and 132 asymmetric ones, ranging from minimum-time to linear-time in synchronization steps. In addition, we make an investigation into several interesting properties of these partial solutions such as swapping general states, a duality between them, inclusion of powers-of-2 solutions, reflected solutions and so on.

**Marcin Dembowski, Barbara Wolnik, Witold Bołt, Jan M. Baetens and Bernard De Baets**

Solving the relaxed density classification problem by means of two-dimensional Affine Continuous Cellular Automata

The density classification problem is one of the most studied problems in the context of computational abilities of cellular automata. Since this problem cannot be solved in the classical sense, we consider a weaker version, by slightly relaxing the assumptions on the output specification. In this paper we discuss this relaxed problem for two-dimensional Affine Continuous Cellular Automata. We focus on finding the most performant rules solving this problem among the density-conserving ones by evaluating ACCAs experimentally for a predefined set of initial configurations.

** Stephanie MacLean, Eric Goles and Marco Montalva-Medel**

On the block invariance of some one-dimensional linear rules

Let’s consider one-dimensional binary cellular automata under periodic boundary conditions. We study the invariance of the periodic configurations of the Wolfram (linear) rules 90 and 150, and linear rules with radius 2, under different deterministic update schemes among which are the parallel and sequential ones (concept known as block invariance). In order to do so, we will focus on update schemes where these rules turn out to be reversible. Specifically, we prove that: rule 90 is invariant if and only if the update scheme considered has no (irreducible) blocks of odd length, and rule 150 is invariant if and only if the update scheme considered has no (irreducible) blocks of length 3p + 2, p ≥ 0. We characterize the invariance of the rule of radius 2 with local function f (xi−2, xi−1 , xi , xi+1, xi+2) = xi−2 ⊕xi−1. Finally, we discuss on the invariance of the remaining linear rules with radius 2.

**Adam Dzedzej, Barbara Wolnik, Anna Nenca, Jan M. Baetens and Bernard De Baets**

Two-dimensional number-conserving cellular automata with von Neumann neighborhood

We present a simple approach for finding all number-conserving two-dimensional cellular automata (CAs) with von Neumann neighborhood in three special cases, being totalistic, binary CAs and 3-state CAs. For that purpose, we use the necessary and sufficient condition for such a CA to be number-conserving that is based on configurations with at most two nonzero entries.

**Marco Montalva Medel, Kévin Perrot, Pedro de Oliveira and Eurico Ruivo**

Sensitivity to synchronism in some boolean automata networks

We study the sensitivity of some Boolean automata networks to changes in their dynamics against deterministic update perturbations. Due to their large number of different dynamics, they can be extremely sensitive to update schedule perturbations, which renders them not robust in this sense, a feature often undesirable in many applications. Here, we study the maximum number of different dynamics in elementary cellular automata, with fixed, cyclic lattices. First, we formally prove the estimate 3n + 2 − 2n+1 for such a number, empirically proposed in a previous work, as well as its sharpness, by proving that some rules actually reach it. Finally, we discuss possible key follow-ups to the present study.

**Aleksander Bołt, Barbara Wolnik and Witold Bołt**

Analysis of the behavior of α-asynchronous Cellular Automata using input-frequencies

In this paper, we study the Elementary α-asynchronous Cellular Automata in the context of their input-frequencies, i.e. frequencies of neighborhoods’ occurrences in the space-time diagrams. Results of the analysis of the changes of these frequencies for different values of the synchrony rate α can help to better understand some of the dynamical properties of α-asynchronous Cellular Automata, for example in the context of the identification problem.