Inversion of 2D cellular automata: Some complexity results
From MaRDI portal
Publication:1341722
DOI10.1016/0304-3975(94)90244-5zbMath0938.68737OpenAlexW1968720345MaRDI QIDQ1341722
Publication date: 27 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)90244-5
Related Items
Tilings: recursivity and regularity ⋮ Complexity of reachability problems for finite discrete dynamical systems ⋮ Structure and Reversibility of 2D von Neumann Cellular Automata Over Triangular Lattice ⋮ Structure and reversibility of 2D hexagonal cellular automata ⋮ Efficient enumeration of three-state two-dimensional number-conserving cellular automata ⋮ 2D Triangular von Neumann Cellular Automata with Periodic Boundary ⋮ Predecessor existence problems for finite discrete dynamical systems ⋮ A two-layer representation of four-state reversible number-conserving 2D cellular automata ⋮ A Random NP-complete problem for inversion of 2D cellular automata ⋮ Theory of cellular automata: a survey ⋮ On the structure of the set of reversible cellular automata ⋮ Garden of Eden configurations for 2-D cellular automata with rule 2460 N ⋮ Cellular automaton growth on \(\mathbb{Z}^2\): Theorems, examples, and problems ⋮ Some applications of propositional logic to cellular automata ⋮ Reversibility of number-conserving 1D cellular automata: unlocking insights into the dynamics for larger state sets ⋮ REVERSIBILITY ALGORITHMS FOR 3-STATE HEXAGONAL CELLULAR AUTOMATA WITH PERIODIC BOUNDARIES ⋮ A new dimension sensitive property for cellular automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reversibility of 2D cellular automata is undecidable
- Reversibility and surjectivity problems of cellular automata
- The surjectivity problem for 2D cellular automata
- Undecidability and nonperiodicity for tilings of the plane
- Tesselations with local transformations
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
- The undecidability of the domino problem
- The complexity of theorem-proving procedures
