Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues

DOI10.1016/j.tcs.2013.11.005zbMath1360.68612OpenAlexW2016560902MaRDI QIDQ385957

Mohammad Hasan, H. S. Yoon

Publication date: 13 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.11.005

zbMATH Keywords

cellular automatasymbolic dynamicsdecidabilitytiling

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15) Symbolic dynamics (37B10)

Related Items (24)

\(m\)-asynchronous cellular automata: from fairness to quasi-fairness ⋮ Chaos and ergodicity are decidable for linear cellular automata over \((\mathbb{Z}/m\mathbb{Z})^n\) ⋮ Reversibility problem of multidimensional finite cellular automata ⋮ Progress, gaps and obstacles in the classification of cellular automata ⋮ Local rule distributions, language complexity and non-uniform cellular automata ⋮ Decidable characterizations of dynamical properties for additive cellular automata over a finite abelian group with applications to data encryption ⋮ Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over \(\mathbb{Z}_p\) ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Computing the periods of preimages in surjective cellular automata ⋮ On the conjugacy problem of cellular automata ⋮ Topological dynamics of nondeterministic cellular automata ⋮ Efficient enumeration of three-state two-dimensional number-conserving cellular automata ⋮ On the dynamical behaviour of linear higher-order cellular automata and its decidability ⋮ Three research directions in non-uniform cellular automata ⋮ A family of sand automata ⋮ Nondeterministic cellular automata ⋮ A generalized neighborhood for cellular automata ⋮ Computational complexity of finite asynchronous cellular automata ⋮ Supercritical probabilistic cellular automata: how effective is the synchronous updating? ⋮ Dynamical behavior of additive cellular automata over finite abelian groups ⋮ Non-uniform cellular automata: classes, dynamics, and decidability ⋮ Turing-completeness of asynchronous non-camouflage cellular automata ⋮ Hierarchy and Expansiveness in 2D Subshifts of Finite Type ⋮ Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(m\)-asynchronous cellular automata: from fairness to quasi-fairness
• Local rule distributions, language complexity and non-uniform cellular automata
• Periodic points for onto cellular automata
• Non-uniform cellular automata: classes, dynamics, and decidability
• Conservation of some dynamical properties for operations on cellular automata
• Sand automata as cellular automata
• On the directional dynamics of additive cellular automata
• Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms
• Reversibility and surjectivity problems of cellular automata
• Dynamical properties of expansive one-sided cellular automata
• On computing the entropy of cellular automata.
• Some properties of cellular automata with equicontinuity points
• Theory of cellular automata: a survey
• Solution of some conjectures about topological properties of linear cellular automata
• Surjective multidimensional cellular automata are non-wandering: a combinatorial proof
• A complete and efficiently computable topological classification of D-dimensional linear cellular automata over \(Z_{m}\)
• A new dimension sensitive property for cellular automata
• Topological Dynamics of 2D Cellular Automata
• Finite entropy for multidimensional cellular automata
• Decidable Properties of 2D Cellular Automata
• A Full Cellular Automaton to Simulate Predator-Prey Systems
• The topological entropy of cellular automata is uncomputable
• Languages, equicontinuity and attractors in cellular automata
• Textile systems for endomorphisms and automorphisms of the shift
• Computing Issues of Asynchronous CA
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• Endomorphisms and automorphisms of the shift dynamical system
• The undecidability of the domino problem

This page was built for publication: Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues