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

DOI10.1016/J.IC.2020.104535MaRDI QIDQ2201794zbMATH OpenOpenAlexFDO

Authors Eric Goles, Diego Maldonado, Pedro Montealegre, Nicolas Ollinger

Publication date 17 September 2020

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.02953

zbMATH Keywords

computational complexitycellular automataP-completenessfast parallel algorithmstotalistic cellular automatafreezing cellular automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cellular automata (computational aspects) (68Q80) Descriptive complexity and finite models (68Q19)

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 $extNC$. - For Turing Universal rules the Stability problem is $extP$-Complete.

Recommendations

• Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata
• On the complexity of asynchronous freezing cellular automata
• Universality in freezing cellular automata
• Freezing, bounded-change and convergent cellular automata
• Computational complexity of the stability problem for elementary cellular automata

Cites work

• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Computational complexity of finite asynchronous cellular automata
• On the complexity of two-dimensional signed majority cellular automata
• On the computational complexity of finite cellular automata
• Parallel Algorithms in Graph Theory: Planarity Testing
• Statistical mechanics of cellular automata
• The complexity of the bootstraping percolation and other problems

Cited in

(7)

• Computational complexity of the stability problem for elementary cellular automata
• Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata
• On the complexity of asynchronous freezing cellular automata
• Universality in freezing cellular automata
• Random expansion method for the generation of complex cellular automata
• On the computational complexity of the freezing non-strict majority automata
• Freezing, bounded-change and convergent cellular automata

This page was built for publication: On the complexity of the stability problem of binary freezing totalistic cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201794)