Published: 13th August 2012 DOI: 10.4204/EPTCS.90 ISSN: 2075-2180

# Proceedings 18th international workshop onCellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires La Marana, Corsica, September 19-21, 2012

Edited by: Enrico Formenti

 Preface Enrico Formenti 1 Invited Presentation: Two-Way Finite Automata: Old and Recent Results Giovanni Pighizzini 3 Invited Presentation: The complexity of some automata networks Eric Goles 21 On Derivatives and Subpattern Orders of Countable Subshifts Ville Salo and Ilkka Törmä 23 Boolean networks synchronism sensitivity and XOR circulant networks convergence time Mathilde Noual, Damien Regnault and Sylvain Sené 37 Topology Inspired Problems for Cellular Automata, and a Counterexample in Topology Ville Salo and Ilkka Törmä 53 Fixed Parameter Undecidability for Wang Tilesets Emmanuel Jeandel and Nicolas Rolin 69 On Nilpotency and Asymptotic Nilpotency of Cellular Automata Ville Salo 86 Entry times in automata with simple defect dynamics Benjamin Hellouin De Menibus and Mathieu Sablik 97 On the Parity Problem in One-Dimensional Cellular Automata Heater Betel, Pedro P. B. de Oliveira and Paola Flocchini 110 Topological arguments for Kolmogorov complexity Alexander Shen and Andrei Romashchenko 127 Local Rules for Computable Planar Tilings Thomas Fernique and Mathieu Sablik 133 Universality of One-Dimensional Reversible and Number-Conserving Cellular Automata Kenichi Morita 142 A Simple Optimum-Time FSSP Algorithm for Multi-Dimensional Cellular Automata Hiroshi Umeo, Kinuo Nishide and Keisuke Kubo 151 Computing by Temporal Order: Asynchronous Cellular Automata Michael Vielhaber 166 Linear functional classes over cellular automata Anaël Grandjean, Gaétan Richard and Véronique Terrier 177 Transductions Computed by One-Dimensional Cellular Automata Martin Kutrib and Andreas Malcher 194 Intrinsic Simulations between Stochastic Cellular Automata Pablo Arrighi, Nicolas Schabanel and Guillaume Theyssier 208 Strictly Temporally Periodic Points in Cellular Automata Alberto Dennunzio, Pietro Di Lena and Luciano Margara 225 Phase Space Invertible Asynchronous Cellular Automata Simon Wacker and Thomas Worsch 236 Topological properties of cellular automata on trees Gabriele Fici and Francesca Fiorenzi 255 A Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings Katsunobu Imai, Takahiro Hatsuda, Victor Poupet and Kota Sato 267

# Preface

This volume contains the proceedings of the 18th International workshop AUTOMATA and the 3rd international symposium JAC.

AUTOMATA workshop series aims at gathering researchers from all over the world working in fundamental aspects of cellular automata and related discrete complex systems. Topics cover (although they are not limited to): dynamics, topological, ergodic and algebraic aspects, algorithmic and complexity issues, emergent properties, formal language processing, symbolic dynamics, models of parallelism and distributed systems, phenomenological descriptions, scientific modeling and practical applications. JAC (Journées Automates Cellulaires) is a bi-annual symposium covering the same topics and was created to have a very high standard international conference in the domain. This one will be the third event of the series after Uzès (2008, France), Turku (2010, Finland).

This year the two events were co-located and they took place at La Marana (Corsica, France) from september 19 to 21, 2012. A huge number of contributions was received. In the aim of keeping the standards very high, only 19 contributions were selected as full papers and appear in these proceedings. Each paper received two or three referee reports. These proceedings contains also the contributions of two invited talks from given from the following renown scientists: Eric Goles (Adolfo Ibanez University, Santiago, Chile) and Giovanni Pighizzini (Università degli Studi di Milano, Milan, Italy).
The chair would like to thank all the members of the program committees, all the referees and sub-referees for their valuable work. He would also like to thank all the authors for their contributions and for the quality of their work which make the author of these few lines proud of editing these proceedings.
 Enrico Formenti Univ. Nice Sophia Antipolis

Program committee
Alberto Dennunzio
Univ. of Milano-Bicocca, Milan, Italy
Giancarlo Mauri
Univ. of Milano-Bicocca, Milan, Italy
Bruno Durand
Univ. de Montpellier 2, Montpellier, France
Kenichi Morita
Hiroshima Univ., Hiroshima, Japan
Paola Flocchini
Univ. of Ottawa, Ottawa, Canada
Pedro de Oliveira
Univ. Presbiteriana Mackenzie, São Paulo, Brazil
Enrico Formenti
Univ. Nice Sophia Antipolis, Nice, France
Ivan Rapaport
Univ. de Chile, Santiago, Chile
Anahi Gajardo
Univ. de Concepción, Concepción, Chile
Hiroshi Umeo
Osaka Electro-Comm. Univ., Osaka, Japan
Jarkko Kari
Univ. of Turku, Turku, Finland
Reem Yassawi
Trent Univ., Trent, Canada
Martin Kutrib
Univ. of Giessen, Giessen, Germany
Thomas Worsch
Karlsruhe Univ., Karlsruhe, Germany
Alejandro Maass
Univ. de Chile, Santiago, Chile

Steering committees
AUTOMATA JAC
Nazim Fatès, Inria Nancy Grand-Est, France Bruno Durand, Univ. de Montpellier 2, France
Eric Goles, Univ. Adolfo Ibañez, Chile Eric Goles, Univ. Adolfo Ibañez, Chile
Jarkko Kari, Univ. of Turku, Finland Nicolas Ollinger, Univ. of Orléans, France
Pedro de Oliveira, Univ. Presb. Mackenzie, Brazil Jarkko Kari, Univ. of Turku, Finland
Thomas Worsch, Karlsruhe Univ., Germany

List of reviewers and sub-reviewers
Alexis BallierJarkko KariGina M. B. Oliveira
Olivier BouréJia LeeFerdinand Peper
Alberto DennunzioAlejandro MaassIvan Rapaport
Bruno DurandAndreas MalcherGaétan Richard
Nazim FatèsLuca ManzoniAndrei Romashchenko
Paola FlocchiniLuciano MargaraPablo Saez
Anahi GajardoGiancarlo MauriSylvain Séné
Pierre GuillonKatjia MeckelPedrag Tosic
Markus HolzerLuiz MonteiroHiroshi Umeo
Katsunobu ImaiAndrès MoreiraBurton Voorhees
Sebastian JakobiKenichi MoritaThomas Worsch
Emmanuel JeandelHenning MortveitReem Yassawi

# The complexity of some automata networks

Eric Goles (Universidad Adolfo Ibañez, Chile)

Let $V$ a finite set of sites or vertices. An Automata Network on $V$ is a triple $A=\left(G,Q,(f_i\,:\;i\in V)\right)$, where $G=(V,E)$ is a simple undirected graph, $Q$ is the set of states, which is assumed to be finite, and $f_i\,:Q^V\to Q$ is the transition function associated to the vertex $i$. The set $Q^V$ is called the set of configurations, and the automaton's global transition function $F\,:\,Q^V\to Q^V$, is constructed with the local transition functions ($f_i\,,\,i\in V$) and with some kind of updating rule, for instance a synchronous or a sequential one. We will be only interested in the case where $Q=\{0,1\}$. Consider the following problem: given an initial configuration $x(0)\in\{0,1\}^{|V|}$ and a vertex $v\in V$, initially passive $(x_v(0)=0)$, determine if there exists a time $T>0$ such that $v$ is active $(x_v(T)=1)$, where $x(t)= F(x(t-1))$ and $F$ is some synchronous global transition function (for example, the strict majority rule). We call this decision problem PER.

First I present the complexity of PER when the global transition function is bootstrap percolation, this is, the rule given by the local functions:

$f_i(x)= \left\{ \begin{array}{ll} 1&\textrm{if}\;x_i=1\\ 1&\textrm{if}\;\sum_{j\in N(i)} x(j)>\frac{|N(i)|}{2}\;\textrm{and}\;x_i=0\\ 0&\textrm{if}\;\sum_{j\in N(i)} x(j)\leq\frac{|N(i)|}{2}\;\textrm{and}\;x_i=0 \end{array} \right.$

In other words, a passive vertex becomes active if the strict majority of its neighbors are active, and thereafter never changes its state. For this rule we show that the problem is in NC if the network belongs to the family of graphs with degree less or equals than $4$, and over this threshold the problem is P-Complete, and we leave open the case of planar networks. The P-Completeness proves were done using simulating a monotone circuit, while the membership in NC was established with an time $O(\log^2(n))$ algorithm on a PRAM, using $O(n^4)$ processors. Consider now a little different rule, the simply majority function:

$f_i(x)=\left\{ \begin{array}{ll} 1&\textrm{if}\;\sum_{j\in N(i)} x(j)>\frac{|N(i)|}{2}\\ 0&\textrm{if}\;\sum_{j\in N(i)} x(j)<\frac{|N(i)|}{2}\\ x_i&\textrm{if}\;\sum_{j\in N(i)} x(j)=\frac{|N(i)|}{2} \end{array} \right.$

For this rule we have that the problem is P-Complete even if the network belongs to the family of planar graphs. This was proven simulating a non-necessarily planar circuit with a planar graph, using a gadget that allows us to cross cables' without mixing information using some traffic lights'.

Finally, I present the complexity of the problem PER with some fixed rule, when we change the iteration mode. That is to say, in this situation the complexity is associated with the update schedule of the network. The usual iteration mode (as we considered above) is the parallel one (every site is updated at the same time). Other one is the sequential mode, sites are updated one by one in a prescribed periodic order. Between this two ones, there are a huge number of updating modes (some sites in parallel, other ones sequentially). It is direct to notice that the complexity of PER with the bootstrap percolation rule is invariant over changes in the iteration mode.

Consider now the rule when the vertices have as local transition function $f_i$ one of the following (arbitrarily chosen and fixed):

$AND(x)=\left\{ \begin{array}{ll} 1&\textrm{if}\;\forall j\in N(i), x(j)=1\\ 0&\textrm{if}\;\exists j\in N(i), x(j)=0 \end{array} \right.$

$OR(x)=\left\{ \begin{array}{ll} 1&\textrm{if}\;\exists j\in N(i), x(j)=1\\ 0&\textrm{if}\;\forall j\in N(i), x(j)=0 \end{array} \right.$

Define the sets $\overline{OR}=\left\{v\in V\;:\;f_v=OR\right\}$, $\overline{AND}=\left\{v\in V\;:\;f_v=AND\right\}$ and assume that in the initial configuration the active vertices (initially in state 1) can be only vertices in $\overline{OR}$. In this case we have that, for a iteration mode given by a word $\omega$: \begin{enumerate} \item if $|\omega|>n$ then PER is P-Complete \item if $|\omega|=n$ \begin{enumerate} \item if we have that $\forall v\in\overline{AND}$, $\forall u\in\overline{OR}\cap N(v)$, $\omega(v)\leq\omega(u)$ or $\omega(v)\geq\omega(u)$, this is, if every AND vertex is updated after or before all its OR neighbors, then the problem is in NC. (Notice that this case includes the synchronous iteration mode). \item Otherwise, the problem is P-Complete. \end{enumerate} \end{enumerate} We conclude that the complexity of PER with this rule highly depends on the iteration mode.

References

[1] Eric Goles, Pedro Montealegre & Ioan Todinca (2012): The Complexity of bootstrap percolation in arbitrary graphs. Theor. Comput. Sci. To appear.
[2] Pedro Montealegre (2012): Thesis of Mathematical Engineering. Ph.D. thesis, Universidad de Chile.