Reversibility and surjectivity problems of cellular automata
From MaRDI portal
Publication:1318474
DOI10.1016/S0022-0000(05)80025-XzbMath0802.68090OpenAlexW2040657429WikidataQ56474284 ScholiaQ56474284MaRDI QIDQ1318474
Publication date: 11 December 1994
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80025-x
undecidabilitydynamical systemssurjectivityreversibilitycellular automatontiling of the planedomino problem
Cellular automata (computational aspects) (68Q80) Combinatorial aspects of tessellation and tiling problems (05B45)
Related Items (76)
Number-conserving cellular automata I: Decidability. ⋮ \(m\)-asynchronous cellular automata: from fairness to quasi-fairness ⋮ On the size of the inverse neighborhoods for one-dimensional reversible cellular automata ⋮ Tilings: recursivity and regularity ⋮ Intrinsic universality of a 1-dimensional reversible Cellular Automaton ⋮ Inversion of 2D cellular automata: Some complexity results ⋮ The surjectivity problem for 2D cellular automata ⋮ A tight linear bound on the synchronization delay of bijective automata ⋮ Real-time reversible iterative arrays ⋮ Bounds on Non-surjective Cellular Automata ⋮ (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata ⋮ Aperiodic points in $\mathbb Z^2$-subshifts ⋮ Reversibility problem of multidimensional finite cellular automata ⋮ Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues ⋮ Progress, gaps and obstacles in the classification of cellular automata ⋮ Reversible and Irreversible Computations of Deterministic Finite-State Devices ⋮ Statistical mechanics of surjective cellular automata ⋮ Cellular automata between sofic tree shifts ⋮ The Most General Conservation Law for a Cellular Automaton ⋮ Communication complexity meets cellular automata: necessary conditions for intrinsic universality ⋮ On computing the entropy of cellular automata. ⋮ Topological Dynamics of 2D Cellular Automata ⋮ Number conserving cellular automata. II: Dynamics. ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Effective Projections on Group Shifts to Decide Properties of Group Cellular Automata ⋮ Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage ⋮ Representation of reversible cellular automata with block permutations ⋮ On the conjugacy problem of cellular automata ⋮ On time-symmetry in cellular automata ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE ⋮ Finite entropy for multidimensional cellular automata ⋮ Decidable Properties of 2D Cellular Automata ⋮ Reversible computing and cellular automata -- a survey ⋮ ON A CHARACTERIZATION OF CELLULAR AUTOMATA IN TILINGS OF THE HYPERBOLIC PLANE ⋮ Structure of the invertible CA transformations group ⋮ Hybrid one-dimensional reversible cellular automata are regular ⋮ A Random NP-complete problem for inversion of 2D cellular automata ⋮ Snakes and Cellular Automata: Reductions and Inseparability Results ⋮ Fast reversible language recognition using cellular automata ⋮ Nondeterministic cellular automata ⋮ On the domino problem of the Baumslag-Solitar groups ⋮ Reversibility of linear cellular automata on Cayley trees with periodic boundary condition ⋮ How Can We Construct Reversible Turing Machines in a Very Simple Reversible Cellular Automaton? ⋮ Hybrid Metric Propositional Neighborhood Logics with Interval Length Binders ⋮ On the hierarchy of conservation laws in a cellular automaton ⋮ Towards a neighborhood simplification of tile systems: from Moore to quasi-linear dependencies ⋮ Topological dynamics of cellular automata: dimension matters ⋮ A closed formula for the inverse of a reversible cellular automaton with \((2 R + 1)\)-cyclic rule ⋮ Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata ⋮ Non-uniform cellular automata: classes, dynamics, and decidability ⋮ Theory of cellular automata: a survey ⋮ Embeddings of dynamical systems into cellular automata ⋮ Linear Algebra Based Bounds for One-Dimensional Cellular Automata ⋮ Non-uniform Cellular Automata ⋮ A Cryptosystem Based on the Composition of Reversible Cellular Automata ⋮ About the Garden of Eden Theorems for Cellular Automata in the Hyperbolic Plane ⋮ Perfectly quilted rectangular snake tilings ⋮ The 4-way deterministic tiling problem is undecidable ⋮ On the complexity of asynchronous freezing cellular automata ⋮ Invertible linear cellular automata over \(\mathbb{Z}_m\): Algorithmic and dynamical aspects ⋮ Pre-expansivity in cellular automata ⋮ PERIODIC CONFIGURATIONS OF SUBSHIFTS ON GROUPS ⋮ Lyapunov exponent versus expansivity and sensitivity in cellular automata ⋮ Decidability in Group Shifts and Group Cellular Automata ⋮ Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties ⋮ Some applications of propositional logic to cellular automata ⋮ Characterizations of periods of multi-dimensional shifts ⋮ Real-Time Reversible One-Way Cellular Automata ⋮ A new dimension sensitive property for cellular automata ⋮ Decidability and undecidability in cellular automata ⋮ Computation in reversible cellular automata ⋮ Computation theoretic aspects of cellular automata ⋮ Reversibility of 2D cellular automata is undecidable ⋮ Invertible cellular automata: A review ⋮ From logic to tiling
Cites Work
- Reversibility of 2D cellular automata is undecidable
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Reversibility and surjectivity problems of cellular automata
