EPTCS 90
Proceedings 18th international workshop on
Cellular Automata and Discrete Complex Systems
and 3rd international symposium
Journées Automates Cellulaires
La Marana, Corsica, September 1921, 2012
Edited by: Enrico Formenti
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 biannual 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 colocated 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 subreferees 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 MilanoBicocca, Milan, Italy 
Giancarlo Mauri Univ. of MilanoBicocca, 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 ElectroComm. 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 GrandEst, 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 subreviewers 
Alexis Ballier  Jarkko Kari  Gina M. B. Oliveira

Olivier Bouré  Jia Lee  Ferdinand Peper

Alberto Dennunzio  Alejandro Maass  Ivan Rapaport

Bruno Durand  Andreas Malcher  Gaétan Richard

Nazim Fatès  Luca Manzoni  Andrei Romashchenko

Paola Flocchini  Luciano Margara  Pablo Saez

Anahi Gajardo  Giancarlo Mauri  Sylvain Séné

Pierre Guillon  Katjia Meckel  Pedrag Tosic

Markus Holzer  Luiz Monteiro  Hiroshi Umeo

Katsunobu Imai  Andrès Moreira  Burton Voorhees

Sebastian Jakobi  Kenichi Morita  Thomas Worsch

Emmanuel Jeandel  Henning Mortveit  Reem Yassawi

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(t1))$ 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 PComplete, and we leave open the case of planar networks. The PCompleteness 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 PComplete even if the network belongs to the family of planar graphs. This was proven simulating a nonnecessarily 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 PComplete
\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 PComplete.
\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.