Decidability and undecidability in cellular automata
From MaRDI portal
Publication:2869780
Recommendations
Cites work
- A characterization of cellular automata generated by idempotents on the full shift
- A complete and efficiently computable topological classification of D-dimensional linear cellular automata over \(Z_{m}\)
- A small aperiodic set of Wang tiles
- Additive conserved quantities in discrete-time lattice dynamical systems
- An aperiodic set of 13 Wang tiles
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- Endomorphisms and automorphisms of the shift dynamical system
- Ergodicity, transitivity, and regularity for linear cellular automata over \(\mathbb{Z}_m\)
- Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms
- Fixed-point tile sets and their applications
- Languages, equicontinuity and attractors in cellular automata
- Linear cellular automata over \(Z_ m\)
- Lyapunov exponent versus expansivity and sensitivity in cellular automata
- Number-conserving cellular automata I: Decidability.
- On computing the entropy of cellular automata.
- On the Limit Sets of Cellular Automata
- On the hierarchy of conservation laws in a cellular automaton
- On time-symmetry in cellular automata
- Periodicity and Immortality in Reversible Computing
- Proving theorems by pattern recognition I
- Remarks on Berger's paper on the domino problem
- Reversibility and surjectivity problems of cellular automata
- Reversibility of 2D cellular automata is undecidable
- Rice's theorem for the limit sets of cellular automata
- Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata
- Snakes and cellular automata: reductions and inseparability results
- The 4-way deterministic tiling problem is undecidable
- The Nilpotency Problem of One-Dimensional Cellular Automata
- The Tiling Problem Revisited (Extended Abstract)
- The surjectivity problem for 2D cellular automata
- The topological entropy of cellular automata is uncomputable
- Theory of cellular automata: a survey
- Transitive Cellular Automata are Sensitive
- Undecidability and nonperiodicity for tilings of the plane
Cited in
(23)- Linear cellular automata and decidability
- scientific article; zbMATH DE number 1962850 (Why is no real title available?)
- Non-uniform cellular automata: classes, dynamics, and decidability
- Effective Projections on Group Shifts to Decide Properties of Group Cellular Automata
- Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata
- scientific article; zbMATH DE number 1223710 (Why is no real title available?)
- Cellular automata, decidability and phasespace
- Decidability of sensitivity and equicontinuity for linear higher-order cellular automata
- An automaton group with undecidable order and Engel problems
- Subshifts with sparse traces
- Reversibility and surjectivity problems of cellular automata
- On the undecidability of attractor properties for cellular automata
- Cellular automata: descriptional complexity and decidability
- Mathematical Foundations of Computer Science 2004
- A decidability result for the halting of cellular automata on the pentagrid
- The immortality problem for Lag systems
- Decidable Properties of 2D Cellular Automata
- Extensions of certain transitive CA with finite sets of \(m\)-periodic points
- Two-dimensional languages and cellular automata
- scientific article; zbMATH DE number 522847 (Why is no real title available?)
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Cellular automata, tilings and (un)computability
- scientific article; zbMATH DE number 3972191 (Why is no real title available?)
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)
