Complexity-theoretic aspects of expanding cellular automata
From MaRDI portal
Publication:2278565
DOI10.1007/978-3-030-20981-0_2zbMath1425.68284arXiv1902.05487OpenAlexW3098341576MaRDI QIDQ2278565
Publication date: 5 December 2019
Full work available at URL: https://arxiv.org/abs/1902.05487
Cellular automata (computational aspects) (68Q80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items (3)
Complexity-theoretic aspects of expanding cellular automata ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
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
- 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
