Talk Abstracts

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