Reversibility and surjectivity problems of cellular automata
From MaRDI portal
Publication:1318474
DOI10.1016/S0022-0000(05)80025-XzbMath0802.68090WikidataQ56474284 ScholiaQ56474284MaRDI QIDQ1318474
Publication date: 11 December 1994
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
undecidability; dynamical systems; surjectivity; reversibility; cellular automaton; tiling of the plane; domino problem
68Q80: Cellular automata (computational aspects)
05B45: Combinatorial aspects of tessellation and tiling problems
Related Items
Representation of reversible cellular automata with block permutations, Hybrid Metric Propositional Neighborhood Logics with Interval Length Binders, Linear Algebra Based Bounds for One-Dimensional Cellular Automata, Characterizations of periods of multi-dimensional shifts, Real-Time Reversible One-Way Cellular Automata, \(m\)-asynchronous cellular automata: from fairness to quasi-fairness, Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues, Cellular automata between sofic tree shifts, On time-symmetry in cellular automata, Groups, graphs, languages, automata, games and second-order monadic logic, Nondeterministic cellular automata, Towards a neighborhood simplification of tile systems: from Moore to quasi-linear dependencies, Topological dynamics of cellular automata: dimension matters, Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata, A Random NP-complete problem for inversion of 2D cellular automata, Non-uniform cellular automata: classes, dynamics, and decidability, Computation theoretic aspects of cellular automata, Reversibility of 2D cellular automata is undecidable, Invertible cellular automata: A review, Real-time reversible iterative arrays, Statistical mechanics of surjective cellular automata, Reversible computing and cellular automata -- a survey, Fast reversible language recognition using cellular automata, Perfectly quilted rectangular snake tilings, The 4-way deterministic tiling problem is undecidable, Invertible linear cellular automata over \(\mathbb{Z}_m\): Algorithmic and dynamical aspects, Lyapunov exponent versus expansivity and sensitivity in cellular automata, Inversion of 2D cellular automata: Some complexity results, The surjectivity problem for 2D cellular automata, On computing the entropy of cellular automata., Number conserving cellular automata. II: Dynamics., From logic to tiling, Reversibility of linear cellular automata on Cayley trees with periodic boundary condition, On the hierarchy of conservation laws in a cellular automaton, Theory of cellular automata: a survey, Number-conserving cellular automata I: Decidability., On the size of the inverse neighborhoods for one-dimensional reversible cellular automata, Tilings: recursivity and regularity, Structure of the invertible CA transformations group, A tight linear bound on the synchronization delay of bijective automata, Reversibility problem of multidimensional finite cellular automata, Hybrid one-dimensional reversible cellular automata are regular, A new dimension sensitive property for cellular automata, About the Garden of Eden Theorems for Cellular Automata in the Hyperbolic Plane, Decidability and undecidability in cellular automata, Computation in reversible cellular automata, Reversible and Irreversible Computations of Deterministic Finite-State Devices, Snakes and Cellular Automata: Reductions and Inseparability Results, Bounds on Non-surjective Cellular Automata, (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata, The Most General Conservation Law for a Cellular Automaton, Topological Dynamics of 2D Cellular Automata, THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE, Finite entropy for multidimensional cellular automata, Decidable Properties of 2D Cellular Automata, ON A CHARACTERIZATION OF CELLULAR AUTOMATA IN TILINGS OF THE HYPERBOLIC PLANE, Embeddings of dynamical systems into cellular automata, Non-uniform Cellular Automata, A Cryptosystem Based on the Composition of Reversible Cellular Automata, PERIODIC CONFIGURATIONS OF SUBSHIFTS ON GROUPS, Some applications of propositional logic to cellular automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
