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, 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, 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, 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, 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, Hybrid one-dimensional reversible cellular automata are regular, A new dimension sensitive property for cellular automata, Decidability and undecidability in cellular automata, Computation in reversible cellular automata, 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
- 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
