Complexity-theoretic aspects of expanding cellular automata

DOI10.1007/s11047-020-09814-2zbMath1530.68181MaRDI QIDQ6195134

Augusto Modanese

Publication date: 16 February 2024

Published in: Natural Computing (Search for Journal in Brave)

zbMATH Keywords

computational complexitycellular automatavarying acceptance conditions

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Unnamed Item
• Unnamed Item
• Graph automata: Natural expression of self-reproduction
• Fast language acceptance by shrinking cellular automata
• Fast parallel language recognition by cellular automata
• Parallel language recognition in constant time by cellular automata
• On truth-table reducibility to SAT
• A comparison of polynomial time reducibilities
• Causal graph dynamics
• Complexity-theoretic aspects of expanding cellular automata
• A characterization of constant-time cellular automata computation
• Shrinking and Expanding Cellular Automata
• Bounded Query Classes
• Reconfigurable cellular computers
• Relativization of questions about log space computability
• Computational Complexity
• Shrinking One-Way Cellular Automata
• Simple Computation-Universal Cellular Spaces
• The complexity of theorem-proving procedures

This page was built for publication: Complexity-theoretic aspects of expanding cellular automata