Reversibility of 2D cellular automata is undecidable

Cites Work

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
Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
Undecidability and nonperiodicity for tilings of the plane
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)

Cited In (63)

Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumeration
Reversible causal graph dynamics: invertibility, block representation, vertex-preservation
The Entropy and Reversibility of Cellular Automata on Cayley Tree
Replication of spatial patterns with reversible and additive cellular automata
Two-dimensional rotation-symmetric number-conserving cellular automata
A survey of cellular automata: types, dynamics, non-uniformity and applications
2D linear CA with mixing boundary conditions and reversibility
Irreversibility of 2D linear CA and Garden of Eden
Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over \(\mathbb{Z}_p\)
Cellular automata between sofic tree shifts
Reversibility of non-saturated linear cellular automata on finite triangular grids
PERIODIC CONFIGURATIONS OF SUBSHIFTS ON GROUPS
Reversibility vs Local Creation/Destruction
Recurrent Misconceptions in the Study of CA Reversibility on Triangular Grids
Decidability and undecidability in cellular automata
A two-layer representation of four-state reversible number-conserving 2D cellular automata
ON THE REVERSIBILITY OF 150 WOLFRAM CELLULAR AUTOMATA
Inversion of 2D cellular automata: Some complexity results
The surjectivity problem for 2D cellular automata
CELLULAR LEARNING AUTOMATA BASED DYNAMIC CHANNEL ASSIGNMENT ALGORITHMS
Some applications of propositional logic to cellular automata
Classifying circular cellular automata
An overview of quantum cellular automata
Reversibility of general 1D linear cellular automata over the binary field \(\mathbb{Z}_2\) under null boundary conditions
Efficient exhaustive listings of reversible one dimensional cellular automata
Theory of cellular automata: a survey
Reversibility and surjectivity problems of cellular automata
Surprising Areas in the Quest for Small Universal Devices
Groups, graphs, languages, automata, games and second-order monadic logic
How to turn a second-order cellular automaton into a lattice gas: a new inversion scheme
Wavefront cellular learning automata
Intrinsic universality of a 1-dimensional reversible Cellular Automaton
Reversible space-time simulation of cellular automata
An order-preserving property of additive invariants for Takesue-type reversible cellular automata
Invertible cellular automata: A review
Two-dimensional cellular automata recognizer
Structure and Reversibility of 2D von Neumann Cellular Automata Over Triangular Lattice
On the structure of the set of reversible cellular automata
Reversibility algorithms for 3-state hexagonal cellular automata with periodic boundaries
Reversibility problem of multidimensional finite cellular automata
Structure and reversibility of 2D hexagonal cellular automata
Parallel recognition of rational languages in plane cellular automata
Snakes and Cellular Automata: Reductions and Inseparability Results
2D Triangular von Neumann Cellular Automata with Periodic Boundary
When-and how-can a cellular automaton be rewritten as a lattice gas?
Reversible cellular automaton able to simulate any other reversible one using partitioning automata
On time-symmetry in cellular automata
Reversible Causal Graph Dynamics
Reversibility of linear cellular automata on Cayley trees with periodic boundary condition
Invertible linear cellular automata over \(\mathbb{Z}_m\): Algorithmic and dynamical aspects
A split-and-perturb decomposition of number-conserving cellular automata
Reversibility of number-conserving 1D cellular automata: unlocking insights into the dynamics for larger state sets
Emergence of universal global behavior from reversible local transitions in asynchronous systems
Nondeterministic cellular automata
Efficient enumeration of three-state two-dimensional number-conserving cellular automata
Self-organising behaviour in the presence of negative externalities: a conceptual model of commuter choice
Cellular automaton growth on \(\mathbb{Z}^2\): Theorems, examples, and problems
Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage
Graph-theoretical characterization of invertible cellular automata
CELLULAR AUTOMATA OVER SEMI-DIRECT PRODUCT GROUPS: REDUCTION AND INVERTIBILITY RESULTS
Garden of Eden configurations for 2-D cellular automata with rule 2460 N
A Random NP-complete problem for inversion of 2D cellular automata
Ternary reversible number-conserving cellular automata are trivial

This page was built for publication: Reversibility of 2D cellular automata is undecidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q807043)