|   | 
Details
   web
Record
Author Goles, E.; Maldonado, D.; Montealegre, P.; Ollinger, N.
Title On the complexity of the stability problem of binary freezing totalistic cellular automata Type
Year 2020 Publication Information And Computation Abbreviated Journal Inf. Comput.
Volume 274 Issue Pages 21 pp
Keywords Cellular automata; Computational complexity; Freezing cellular automata; Totalistic cellular automata; Fast parallel algorithms; P-Complete
Abstract 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. (C) 2020 Elsevier Inc. All rights reserved.
Address [Goles, Eric; Montealegre, Pedro] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: eric.chacc@uai.cl;
Corporate Author Thesis
Publisher Academic Press Inc Elsevier Science Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title (down)
Series Volume Series Issue Edition
ISSN 0890-5401 ISBN Medium
Area Expedition Conference
Notes WOS:000573267700008 Approved
Call Number UAI @ alexi.delcanto @ Serial 1238
Permanent link to this record