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 19-21, 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 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 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(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.