The surjectivity problem for 2D cellular automata
From MaRDI portal
Publication:1342866
DOI10.1016/S0022-0000(05)80077-7zbMATH Open0938.68728MaRDI QIDQ1342866FDOQ1342866
Authors: Bruno Durand 
Publication date: 21 June 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Cites Work
- On the Limit Sets of Cellular Automata
- Reversibility and surjectivity problems of cellular automata
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- The undecidability of the domino problem
- Tesselations with local transformations
- Title not available (Why is that?)
- Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
- Undecidability and nonperiodicity for tilings of the plane
- Reversibility of 2D cellular automata is undecidable
- Invertible cellular automata: A review
- One-way cellular automata on Cayley graphs
- Title not available (Why is that?)
Cited In (8)
- Decidability and undecidability in cellular automata
- Inversion of 2D cellular automata: Some complexity results
- Number-conserving cellular automata I: Decidability.
- Snakes and cellular automata: reductions and inseparability results
- A new dimension sensitive property for cellular automata
- Tilings: recursivity and regularity
- Embeddings of dynamical systems into cellular automata
- A Random NP-complete problem for inversion of 2D cellular automata
This page was built for publication: The surjectivity problem for 2D cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1342866)
