Decidability and undecidability in cellular automata
From MaRDI portal
Publication:2869780
DOI10.1080/03081079.2012.695895zbMath1277.68152WikidataQ62045912 ScholiaQ62045912MaRDI QIDQ2869780
Publication date: 6 January 2014
Published in: International Journal of General Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/03081079.2012.695895
68Q80: Cellular automata (computational aspects)
05B45: Combinatorial aspects of tessellation and tiling problems
Related Items
Unnamed Item, Subshifts with sparse traces, An automaton group with undecidable order and Engel problems
Cites Work
- Unnamed Item
- Fixed-point tile sets and their applications
- On time-symmetry in cellular automata
- Reversibility of 2D cellular automata is undecidable
- The 4-way deterministic tiling problem is undecidable
- Linear cellular automata over \(Z_ m\)
- An aperiodic set of 13 Wang tiles
- A small aperiodic set of Wang tiles
- Additive conserved quantities in discrete-time lattice dynamical systems
- Lyapunov exponent versus expansivity and sensitivity in cellular automata
- Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms
- Reversibility and surjectivity problems of cellular automata
- Rice's theorem for the limit sets of cellular automata
- The surjectivity problem for 2D cellular automata
- On computing the entropy of cellular automata.
- Ergodicity, transitivity, and regularity for linear cellular automata over \(\mathbb{Z}_m\)
- On the hierarchy of conservation laws in a cellular automaton
- Theory of cellular automata: a survey
- Number-conserving cellular automata I: Decidability.
- A complete and efficiently computable topological classification of D-dimensional linear cellular automata over \(Z_{m}\)
- Undecidability and nonperiodicity for tilings of the plane
- Remarks on Berger's paper on the domino problem
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- A Characterization of Cellular Automata Generated by Idempotents on the Full Shift
- Snakes and Cellular Automata: Reductions and Inseparability Results
- On the Limit Sets of Cellular Automata
- Proving theorems by pattern recognition I
- Periodicity and Immortality in Reversible Computing
- The Tiling Problem Revisited (Extended Abstract)
- The Nilpotency Problem of One-Dimensional Cellular Automata
- The topological entropy of cellular automata is uncomputable
- Languages, equicontinuity and attractors in cellular automata
- Transitive Cellular Automata are Sensitive
- Endomorphisms and automorphisms of the shift dynamical system
