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

DOI10.1016/j.ic.2020.104535zbMath1455.68108arXiv1912.02953OpenAlexW3010360050MaRDI QIDQ2201794

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

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 automatafast parallel algorithmsP-completenesstotalistic cellular automatafreezing cellular automata

Mathematics Subject Classification ID

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

Related Items (2)

Random expansion method for the generation of complex cellular automata ⋮ On the complexity of asynchronous freezing cellular automata

Cites Work

• The complexity of the bootstraping percolation and other problems
• Computational complexity of finite asynchronous cellular automata
• On the computational complexity of finite cellular automata
• On the complexity of two-dimensional signed majority cellular automata
• Statistical mechanics of cellular automata
• Parallel Algorithms in Graph Theory: Planarity Testing
• Unnamed Item
• Unnamed Item
• Unnamed Item

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