TY - GEN
T1 - Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata
AU - Goles, Eric
AU - Maldonado, Diego
AU - Montealegre-Barba, Pedro
AU - Ollinger, Nicolas
N1 - Publisher Copyright:
© 2018, Springer Nature Switzerland AG.
PY - 2018
Y1 - 2018
N2 - In this paper we study the family of two-state Totalistic Freezing Cellular Automata (FTCA) defined over the triangular grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only of the sum of its active neighbors. We study the family of FTCA in the context of asynchronous updating schemes (calling them FTACA), meaning that at each time-step only one cell is updated. The sequence of updated sites is called a sequential updating schemes. Given configuration, we say that a site is stable if it remains in the same state over any sequential updating scheme. In this context, we consider the Asynchronous Stability problem, consisting in decide whether there is a sequential updating scheme such that an inactive cell becomes active. We show that in this family the problem is NC, i.e. it can be solved by fast-parallel algorithms.
AB - In this paper we study the family of two-state Totalistic Freezing Cellular Automata (FTCA) defined over the triangular grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only of the sum of its active neighbors. We study the family of FTCA in the context of asynchronous updating schemes (calling them FTACA), meaning that at each time-step only one cell is updated. The sequence of updated sites is called a sequential updating schemes. Given configuration, we say that a site is stable if it remains in the same state over any sequential updating scheme. In this context, we consider the Asynchronous Stability problem, consisting in decide whether there is a sequential updating scheme such that an inactive cell becomes active. We show that in this family the problem is NC, i.e. it can be solved by fast-parallel algorithms.
UR - http://www.scopus.com/inward/record.url?scp=85053898589&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-99813-8_37
DO - 10.1007/978-3-319-99813-8_37
M3 - Conference contribution
AN - SCOPUS:85053898589
SN - 9783319998121
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 406
EP - 415
BT - Cellular Automata - 13th International Conference on Cellular Automata for Research and Industry, ACRI 2018, Proceedings
A2 - Nishinari, Katsuhiro
A2 - Mauri, Giancarlo
A2 - Dennunzio, Alberto
A2 - Manzoni, Luca
A2 - El Yacoubi, Samira
PB - Springer Verlag
T2 - 13th International Conference on Cellular Automata for Research and Industry, ACRI 2018
Y2 - 17 September 2018 through 21 September 2018
ER -