The surjectivity problem for 2D cellular automata
From MaRDI portal
Publication:1342866
DOI10.1016/S0022-0000(05)80077-7zbMath0938.68728MaRDI QIDQ1342866
Publication date: 21 June 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items
Number-conserving cellular automata I: Decidability. ⋮ Tilings: recursivity and regularity ⋮ Inversion of 2D cellular automata: Some complexity results ⋮ A Random NP-complete problem for inversion of 2D cellular automata ⋮ Snakes and Cellular Automata: Reductions and Inseparability Results ⋮ Embeddings of dynamical systems into cellular automata ⋮ A new dimension sensitive property for cellular automata ⋮ Decidability and undecidability in cellular automata
Cites Work
- Unnamed Item
- Unnamed Item
- Reversibility of 2D cellular automata is undecidable
- Invertible cellular automata: A review
- Reversibility and surjectivity problems of cellular automata
- One-way cellular automata on Cayley graphs
- Undecidability and nonperiodicity for tilings of the plane
- Tesselations with local transformations
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- On the Limit Sets of Cellular Automata
- Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
- The undecidability of the domino problem
