A universal cellular automaton in the hyperbolic plane.
From MaRDI portal
Publication:1401276
DOI10.1016/S0304-3975(02)00660-6zbMath1045.68095OpenAlexW1988062990MaRDI QIDQ1401276
Francine Herrmann, Maurice Margenstern
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00660-6
Related Items (6)
In some curved spaces, one can solve NP-hard problems in polynomial time ⋮ A Weakly Universal Cellular Automaton in the Pentagrid with Five States ⋮ A universal cellular automaton on the heptagrid of the hyperbolic plane with four states ⋮ Unnamed Item ⋮ Surprising Areas in the Quest for Small Universal Devices ⋮ A Universal Cellular Automaton on the Ternary Heptagrid
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Undecidable tiling problems in the hyperbolic plane
- One-way cellular automata on Cayley graphs
- Introduction to hyperbolic geometry
- NP problems are tractable in the space of cellular automata in the hyperbolic plane
- Two railway circuits: A universal circuit and an NP-difficult one
This page was built for publication: A universal cellular automaton in the hyperbolic plane.
