Decidability and undecidability in cellular automata
From MaRDI portal
Publication:2869780
DOI10.1080/03081079.2012.695895zbMATH Open1277.68152OpenAlexW2123070771WikidataQ62045912 ScholiaQ62045912MaRDI QIDQ2869780FDOQ2869780
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
Recommendations
Combinatorial aspects of tessellation and tiling problems (05B45) Cellular automata (computational aspects) (68Q80)
Cites Work
- An aperiodic set of 13 Wang tiles
- Theory of cellular automata: a survey
- Endomorphisms and automorphisms of the shift dynamical system
- On the Limit Sets of Cellular Automata
- Languages, equicontinuity and attractors in cellular automata
- Reversibility and surjectivity problems of cellular automata
- Remarks on Berger's paper on the domino problem
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- The Nilpotency Problem of One-Dimensional Cellular Automata
- The topological entropy of cellular automata is uncomputable
- Transitive Cellular Automata are Sensitive
- Periodicity and Immortality in Reversible Computing
- On time-symmetry in cellular automata
- Lyapunov exponent versus expansivity and sensitivity in cellular automata
- Undecidability and nonperiodicity for tilings of the plane
- Fixed-point tile sets and their applications
- Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms
- On computing the entropy of cellular automata.
- A complete and efficiently computable topological classification of D-dimensional linear cellular automata over \(Z_{m}\)
- Title not available (Why is that?)
- A small aperiodic set of Wang tiles
- Number-conserving cellular automata I: Decidability.
- Reversibility of 2D cellular automata is undecidable
- The Tiling Problem Revisited (Extended Abstract)
- Additive conserved quantities in discrete-time lattice dynamical systems
- Rice's theorem for the limit sets of cellular automata
- On the hierarchy of conservation laws in a cellular automaton
- Linear cellular automata over \(Z_ m\)
- Ergodicity, transitivity, and regularity for linear cellular automata over \(\mathbb{Z}_m\)
- A Characterization of Cellular Automata Generated by Idempotents on the Full Shift
- The surjectivity problem for 2D cellular automata
- Proving theorems by pattern recognition I
- The 4-way deterministic tiling problem is undecidable
- Snakes and Cellular Automata: Reductions and Inseparability Results
Cited In (15)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Decidability of sensitivity and equicontinuity for linear higher-order cellular automata
- Subshifts with sparse traces
- An automaton group with undecidable order and Engel problems
- Reversibility and surjectivity problems of cellular automata
- Title not available (Why is that?)
- Mathematical Foundations of Computer Science 2004
- The immortality problem for Lag systems
- Decidable Properties of 2D Cellular Automata
- Two-dimensional languages and cellular automata
- Title not available (Why is that?)
- Cellular automata, tilings and (un)computability
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Title not available (Why is that?)
This page was built for publication: Decidability and undecidability in cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2869780)
