Invited talks | Full papers | Exploratory papers
Invited Talks
Andreas Deutsch
Cellular automaton models for collective cell behavior
Collective dynamics of interacting cell populations drives key processes in biological tissue formation and maintenance under normal and diseased conditions. Lattice-gas cellular automata have proven successful to model and analyze collective migration and pattern formation emerging from specific cell interactions. Here, we introduce lattice-gas cellular automaton models for collective cell migration, clustering, growth and invasion and demonstrate how analysis of the models allows for predicting emerging properties at the individual cell and the cell population level. Finally, we discuss applications of the growth and invasion models to glioma tumours.
REFERENCE: Deutsch, S. Dormann: Cellular Automaton Modeling of Biological Pattern Formation: Characterization, Applications, and Analysis, Birkhauser, Boston, 2005 (2nd ed. 2015)
Turlough Neary
Tag systems and the complexity of simple programs
We review time complexity and program size results for universal Turing machines, tag systems, cellular automata, and other simple models of computation. Since the 1960s the smallest known universal Turing machines and many other simple models of computation suffered from an exponential slowdown when simulating Turing machines. We discuss results that show that the simplest known models of computation including the smallest known universal Turing machines and the elementary cellular automaton Rule 110 are in fact efficient (polynomial time) simulators of Turing machines. We also recall a recent result where the halting problem for tag systems with only 2 symbols (the minimum possible) is proved undecidable. This result has already yielded applications including a significant improvement on previous undecidability bounds for the Post correspondence problem and the matrix mortality problem.
Ville Salo
Groups and monoids of cellular automata
We discuss groups and monoids defined by cellular automata on full shifts, sofic shifts, minimal subshifts, countable subshifts and coded and synchronized systems. Both purely group-theoretic properties and issues of decidability are considered.
Luke Schaeffer
A Physically Universal Quantum Cellular Automaton
We explore a quantum version of Janzing’s “physical universality”, a notion of computational universality for cellular automata which requires computations to be done directly on the cells. We discuss physical universality in general, the issues specific to the quantum setting, and give an example of a quantum cellular automaton achieving a quantum definition of physical universality.
Full Papers
Abhijin Adiga, Chris J Kuhlman, Henning S Mortveit and Sichao Wu
Effect of Graph Structure on the Limit Sets of Threshold Dynamical Systems
We study the attractor structure of standard block-sequential threshold dynamical systems. In a block-sequential update, the vertex set of the graph is partitioned into blocks, and the blocks are updated sequentially while the vertices within blocks are updated in parallel. There are several notable results from the past concerning the two extreme cases of block-sequential update: (i) sequential update where each block is a singleton and (ii) parallel update where the entire vertex set is one block. While parallel threshold systems can have limit cycles of length at most two, sequential systems can have only fixed points. However, Goles and Montealegre [5] showed the existence of block-sequential threshold systems that have arbitrarily long limit cycles. Motivated by this result, we study how the underlying graph structure influences the limit cycle structure of block-sequential systems. We derive a sufficient condition on the graph structure so that the system has only fixed points as limit cycles. We also demonstrate several well-known graph families that satisfy this condition.
Matthew Cook, Urban Larsson and Turlough Neary
A Cellular Automaton for Blocking Queen Games
We show that the winning positions of a certain type of two-player game form interesting patterns which often defy analysis, yet can be computed by a cellular automaton. The game, known as Blocking Wythoff Nim, consists of moving a queen as in chess, but always towards (0,0), and it may not be moved to any of k − 1 temporarily “blocked” positions specified on the previous turn by the other player. The game ends when a player wins by blocking all possible moves of the other player. The value of k is a parameter that defines the game, and the pattern of winning positions can be very sensitive to k. We give methods that can be used to analyze these patterns for specific values of k. As k becomes large, parts of the pattern of winning positions converge to recurring chaotic patterns that are independent of k. The patterns for large k display a surprising amount of self-organization at many scales.
Kari Eloranta
Hard Core via PCA: entropy bounds
We establish lower bounds for the entropy of the Hard Core Model/Independent Sets on a few 2-d lattices. Our PCA based sequential fill-in method is unbiased thereby in principle yielding arbitrarily good estimates for the topological entropy. Additionally the procedure gives some insight on the support of the measure of maximal entropy.
Jeremias Epperlein
Classification of Elementary Cellular Automata up to Topological Conjugacy
Topological conjugacy is the natural notion of isomorphism in topological dynamics. It can be used as a very fine grained classification scheme for cellular automata. In this article, we investigate different invariants for topological conjugacy in order to distinguish between non-conjugate systems. In particular we show how to compute the cardinality of the set of points with minimal period n for one-dimensional CA. Applying these methods to the 256 elementary one-dimensional CA, we show that up to topological conjugacy there are exactly 83 of them.
Nazim Fates
Remarks on the cellular automaton global synchronisation problem
The global synchronisation problem consists in making a cellular automata converge to a homogeneous blinking state from any initial condition. We here study this inverse problem for one-dimensional binary systems with periodic boundary conditions (i.e., rings). For small neighbourhoods, we present results obtained with the formulation of the problem as a SAT problem and the use of SAT solvers. Our observations suggest that it is not possible to solve this problem perfectly with deterministic systems.
Anaël Grandjean and Victor Poupet
L-Convex Polyominoes are Recognizable in Real Time by 2D Cellular Automata
A polyomino is said to be L-convex if any two of its cells are connected by a 4-connected inner path that changes direction at most once. The 2-dimensional language representing such polyominoes has been recently proved to be recognizable by tiling systems by S. Brocchi, A. Frosini, R. Pinzani and S. Rinaldi. In an attempt to compare recognition power of tiling systems and cellular automata, we have proved that this language can be recognized by 2-dimensional cellular automata working on the von Neumann neighborhood in real time.
Although the construction uses a characterization of L-convex polyominoes that is similar to the one used for tiling systems, the real time constraint which has no equivalent in terms of tilings requires the use of techniques that are specific to cellular automata.
Martin Kutrib, Andreas Malcher and Matthias Wendlandt
Shrinking One-Way Cellular Automata
We investigate cellular automata as acceptors for formal languages.
In particular, we consider real-time one-way cellular automata (OCA) with the additional property that during a computation any cell of the OCA has the ability to dissolve itself and we call this model shrinking one-way cellular automata (SOCA). It turns out that real-time SOCA are more powerful than real-time OCA, since they can accept certain linear-time OCA languages. Additionally, a construction is provided that enables real-time SOCA to accept the reversal of real-time iterative array languages. Finally, restricted real-time SOCA are investigated which are allowed to dissolve only a number of cells that is bounded by some function. In this case, an infinite strict hierarchy of language classes is obtained.
Diego Maldonado, Andres Moreira and Anahi Gajardo
Universal Time-symmetric Number-conserving Cellular Automaton
We show the existence of Turing-universal and intrinsically universal cellular automata exhibiting both time symmetry and number conservation; this is achieved by providing a way to simulate reversible CA with time-symmetric CA, which preserves the number-conserving property. We also provide some additional results and observations concerning the simulation relations between reversible, time-symmetric and number-conserving CA in the context of partitioned CA.
Norman Margolus
The ideal energy of classical CA
We provide a natural and fundamental definition of energy and momentum for cellular automata, based on universal bounds on state change and an ideal embedding of invertible finite-state dynamics into quantum dynamics. We test these definitions on two CA models closely related to classical mechanics (one new, the other used in new ways), where we see that the quantities match up with what one might expect.
Luca Mariot and Alberto Leporati
On the Periods of Spatially Periodic Preimages in Linear Bipermutive Cellular Automata
In this paper, we investigate the periods of preimages of spatially periodic configurations in linear bipermutive cellular automata (LBCA). We first show that when the CA is only bipermutive and y is a spatially periodic configuration of period p, the periods of all preimages of y are multiples of p. We then present a connection between preimages of spatially periodic configurations of LBCA and concatenated linear recurring sequences, finding a characteristic polynomial for the latter which depends on the local rule and on the configurations. We finally devise a procedure to compute the period of a single preimage of a spatially periodic configuration y of a given LBCA, and characterise the periods of all preimages of y when the corresponding characteristic polynomial is the product of two distinct irreducible polynomials.
Claudio L.M. Martins and Pedro P.B. de Oliveira
Merging Cellular Automata Rules to Optimise a Solution to the Modulo-n Problem
Understanding how the composition of cellular automata rules can perform predefined computations can contribute to the general notion of emerging computing by means of locally processing components. In this context, a solution has been recently proposed to the Modulo-n Problem, which is the determination of whether the number of 1-bits in a binary string is perfectly divisible by the positive integer n. Here, we show how to optimise that solution in terms of a reduction of the number of rules required, by means of a merging operation involving of the rules´ active state transitions. The potential for a more general usage of the merging operation is also addressed.
Abhijin Adiga, Hilton Galyean, Chris J Kuhlman, Michael Levet, Henning S Mortveit and Sichao Wu
Network Structure and Activity in Boolean Networks
In this paper we extend the notion of activity for Boolean Networks introduced by Shmulevich and Kauffman (2004). Unlike the existing notion, we take into account the actual graph structure of the Boolean Network. As illustrations, we determine the activity of all elementary cellular automata, and d-regular trees and square lattices where the vertex functions are bi-threshold- and logical nor functions.
The notion of activity measures the probability that perturbations in an initial state produces a different successor state than that of the original unperturbed state. Apart from capturing sensitive dependence on initial conditions, activity provides a possible measure for the significance or influence of a variable. Identifying the most active variables may offer insight into design of for example biological experiments of systems modeled by Boolean Networks. We conclude with some open questions and thoughts on directions for future research related to activity.
Ville Salo and Ilkka Törmä
Group-Walking Automata
In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of multi-headed finite automata that walk on Cayley graphs, and use it to define subshifts. We characterize the torsion groups (also known as periodic groups) as those on which the group-walking automata are strictly weaker than Turing machines.
Siamak Taati
Restricted density classification in one dimension
The density classification task is to determine which of the symbols appearing in an array has the majority. A cellular automaton solving this task is required to converge to a uniform configuration with the majority symbol at each site. It is not known whether a one-dimensional cellular automaton with binary alphabet can classify all Bernoulli random configurations almost surely according to their densities. We show that any cellular automaton that washes out finite islands in linear time classifies all Bernoulli random configurations with parameters close to 0 or 1 almost surely correctly. The proof is a direct application of a “percolation” argument, which goes back to Gacs (1986).
Véronique Terrier
Recognition of linear-slender context-free languages by real time one-way cellular automata
A linear-slender context-free language is a context-free language whose number of words of length n is linear in n. Its structure has been finely characterized in a work of Ilie, Rozenberg and Salomaa. Thanks to this characterization, we show that every linear-slender context-free language is recognizable by a real time one-way cellular automaton.
Exploratory papers
Alyssa Adams, Hector Zenil, Eduardo Hermo Reyes and Joost J. Joosten
Effects of a Global Rule on Interacting Cellular Automata
We explore some of the effects of a Global Rule (GR) propagating the interaction between two Elementary Cellular Automata (ECA). The Global Rule is defined as the addition of a local rule that evolves mixed neighborhoods to the two interacting ECA rules. Complexity mea- sures were made on the output of state evolutions of cellular automata (CA) interaction instances to determine the resulting behavior of the interaction. Several Global Rules change the complexity of the state evolution output, which suggests that some complexity is intrinsic to a Global Rule but we also found that some Class 3 or 4 CA rules are more fragile than others to Global Rules, while others are more robust, hence suggesting some intrinsic properties of the rules independent of the Global Rule choice. We provide statistical mappings of ECA exposed to GRs and different initial conditions onto different complexity classes.
Sébastien Autran, Enrico Formenti and Julien Provillard
More Decision Algorithms for Global Properties of 1D CA
This paper proposes a decision algorithm for surjectivity on finite configurations for one-dimensional cellular automata (CA). Moreover, by using the classical decision algorithm for surjectivity and injectivity of Sutner, we provide a simple decision algorithm for openess (although its complexity is unchanged). Finally, a complete implication diagram between global properties of one-dimensional CA is provided.
Mariusz Białecki
An Explanation of the Shape of the Universal Curve of the Earthquake Recurrence Time Distributions by Means of a Cellular Automaton Model
This paper presents an idea for an explanation of a mechanism underlying the shape of the universal curve of the Earthquake Recurrence Time Distributions. The proposed simple stochastic cellular automaton model is reproducing the gamma distribution fit with the proper value of parameter characterizing the Earth’s seismicity and also imitates a deviation from the fit at short interevent times, as observed in real data.
Thus the model suggests an explanation of the universal pattern of
rescaled Earthquake Recurrence Time Distributions in terms of
combinatorial rules for accumulation and abrupt release of seismic energy.
Witold Bolt, Marcin Dembowski, Jan M. Baetens, Bernard De Baets
Solving the Density Classification Problem by Means of Continuous Cellular Automata
The Density Classification Task (DCT) is one of the most studied problems in the context of the computational abilities of Cellular Automata. In this paper we propose a novel, relaxed variant of this task, namely the α-DCT, which might be solved using Continuous Cellular Automata.
Silvio Capobianco, Jarkko Kari, Siamak Taati
Post-surjectivity and Balancedness of Cellular Automata over Groups
We discuss cellular automata over arbitrary finitely generated groups. We call a cellular automaton post-surjective if for any pair of asymptotic configurations, every preimage of one is asymptotic to a preimage of the other. The well known dual concept is pre-injectivity: a cellular automaton is pre-injective if distinct asymptotic configurations have distinct images. We prove that pre-injective, post-surjective cellular automata over surjunctive groups are reversible. In particular, post-surjectivity and reversibility are equivalent notions on amenable groups. We also prove that reversible cellular automata over arbitrary groups are balanced, that is, they preserve the uniform measure on the configuration space.
Rezki Chemlal
Equicontinuity Points and Eigenvalues of One-dimensional Cellular Automata
We want to study the possibility for a one-dimensional cellular automaton to have or not irrational eigenvalues i.e. those of the form e2Iπα where α is irrational and I the complex root of −1.
Henryk Fukś, Joel Midgley-Volpato
An Example of Degenerate Hyperbolicity in a Cellular Automaton with 3 States
We show that a behaviour analogous to degenerate hyperbolicity can occur in nearest-neighbour cellular automata (CA) with three states. We construct a 3-state rule by “lifting” elementary CA rule 140. Such “lifted” rule is equivalent to rule 140 when arguments are restricted to two symbols, otherwise it behaves as identity. We analyze the structure of multi-step preimages of 0, 1 and 2 under this rule by using minimal finite state machines (FSM), and exploit regularities found in these FMS. This allows to construct explicit expressions for densities of 0s and 1s after n iterations of the rule starting from Bernoulli distribution. When the initial Bernoulli distribution is symmetric, the densities of all three symbols converge to their stationary values in linearly-exponential fashion, similarly as in finite-dimensional dynamical systems with hyperbolic fixed point with degenerate eigenvalues.
Juan Carlos García Vázquez, Fernando Sancho Caparrini
Dynamic Behavior of a Non-local Totalistic Cellular Automaton
In this paper we consider a 2D discrete dynamical system based on a totalistic cellular automaton where the neighborhood of each site allows two random nonlocal connections. The system shows a phase transition in the type of dynamic behaviour with order parameter equals to the maximum distance at which the random connections can be done.
Eric Goles, Nicolas Ollinger, Guillaume Theyssier
Introducing Freezing Cellular Automata
We introduce the class of freezing cellular automata (CA): those where the state of a cell can only increase according to some order on states. It contains some well-studied examples like the bootstrap percolation CA or “life without death”, but here we aim at studying the class as a whole and deriving general properties of freezing CA. Our focus is mainly on the complexity of these CA and we show that, if their definition imposes strong constraints on their possible dynamics, they still can produce complex computational behaviors, even in dimension 1. Our main results are that the prediction problem of these CA can be P-complete in dimension 2 or more, but is always NL in dimension 1. Moreover its communication complexity is always at most O(nd−1 log(n)) in dimension d (while it can be Ω(nd) for a CA in general). As another dimension-sensitive property, we show that the nilpotency problem is decidable in dimension 1 but not in higher dimension. Finally, although simpler, we show that one-dimensional freezing CA can still be Turing universal.
Jimmy Jose, Dipanwita Roy Chowdhury
Four Neighbourhood Cellular Automata as Better Cryptographic Primitives
Three-neighbourhood Cellular Automata (CA) are widely studied and accepted as suitable cryptographic primitive. Rule 30, a 3-neighbourhood CA rule, was proposed as an ideal candidate for cryptographic primitive by Wolfram. However, rule 30 was shown to be weak against Meier-Staffelbach attack. The cryptographic properties like diffusion and randomness increase with increase in neighbourhood radius and thus opens the avenue of exploring the cryptographic properties of 4-neighbourhood CA. This work explores whether four-neighbourhood CA can be a better cryptographic primitive. We construct a class of cryptographically suitable 4-neighbourhood nonlinear CA rules that resembles rule 30. One 4-neighbourhood nonlinear CA from this selected class is shown to be resistant against Meier-Staffelbach attack on rule 30, justifying the applicability of 4-neighbourhood CA as a better cryptographic primitives.
Abhrajit Sengupta, Shamit Ghosh, Dipanwita Roy Chowdhury
Dynamic Synthesis and Analysis of Maximum Length Linear and Nonlinear Cellular Automata
Pseudorandom number generators (PRNG) are a central requirement for many cryptographic applications such as key generators, stream ciphers and nonces. However, in contemporary literature the fixed structure of a PRNG leads to a deterministic nature. In this work, we explore the idea of constructing a
dynamically alterable PRNG by exploiting the highly efficient structure of cellular automata (CA). Moreover, nonlinearity being another important aspect of a PRNG, the current paper discusses a way of introducing it in the design to make it cryptographically secure. Next, detailed mathematical analysis of the constructed
PRNG with an emphasis on nonlinearity and statistical properties are presented to show its suitability as a cryptographic primitive.
Dmitry A. Zaitsev
Simulating Cellular Automata by Infinite Synchronous Petri Nets
We construct infinite synchronous Petri nets which directly simulate a one-dimensional cellular automaton with the rule 110. The first net uses inhibitor and read arcs, the second only uses read arcs, and the third uses neither inhibitor nor read arcs. They represent an infinite repetition of a block consisting of (1,3), (2,3), (5,13) places and transitions, respectively, and run in linear time. The third net imposes super-blocks consisting of 3 cyclically repeated blocks. Generalizations of these results on d-dimensional cellular automata is discussed. For finite specification of infinite nets, parametric expressions are employed. The nets are Turing-complete (universal) and have polynomial time complexity.