TY - JOUR

T1 - On the complexity of the stability problem of binary freezing totalistic cellular automata

AU - Goles, Eric

AU - Maldonado, Diego

AU - Montealegre, Pedro

AU - Ollinger, Nicolas

N1 - Funding Information:
Research founded by ECOS-CONICYT C16E01 (E.G.), CONICYT + PAI + CONVOCATORIA NACIONAL SUBVENCÓIN A INSTALACIÓN EN LA ACADEMIA CONVOCATORIA AÑO 2017 + PAI77170068 (P.M.), FONDECYT 11190482 (P.M.), and CONICYT via Programa Regional STIC-AmSud (CoDANet) cód. 19-STIC-03 (E.G. and P.M.).
Publisher Copyright:
© 2020 Elsevier Inc.

PY - 2020/10

Y1 - 2020/10

N2 - In this paper we study the family of two-state Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square 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 on the sum of its active neighbors. We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules, Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the STABILITY problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration. We exploit the properties of the automata in each group to show that: • For Algebraic and Topological Rules the STABILITY problem is in NC. • For Turing Universal rules the STABILITY problem is P-Complete.

AB - In this paper we study the family of two-state Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square 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 on the sum of its active neighbors. We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules, Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the STABILITY problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration. We exploit the properties of the automata in each group to show that: • For Algebraic and Topological Rules the STABILITY problem is in NC. • For Turing Universal rules the STABILITY problem is P-Complete.

KW - Cellular automata

KW - Computational complexity

KW - Fast parallel algorithms

KW - Freezing cellular automata

KW - P-Complete

KW - Totalistic cellular automata

UR - http://www.scopus.com/inward/record.url?scp=85081258703&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2020.104535

DO - 10.1016/j.ic.2020.104535

M3 - Article

AN - SCOPUS:85081258703

VL - 274

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 104535

ER -