Decidable Properties of 2D Cellular Automata

DOI10.1007/978-3-540-85780-8_21MaRDI QIDQ3533017zbMATHOpenAlexFDO

Authors Alberto Dennunzio, Enrico Formenti

Publication date 30 October 2008

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85780-8_21

zbMATH Keywords

cellular automatasymbolic dynamicsdecidability

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Recommendations

• Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues
• From one-dimensional to two-dimensional cellular automata
• Two-dimensional languages and cellular automata
• Decidability and undecidability in cellular automata
• Topological Dynamics of 2D Cellular Automata

Cites work

• scientific article; zbMATH DE number 1333618 (Why is no real title available?)
• scientific article; zbMATH DE number 2042127 (Why is no real title available?)
• scientific article; zbMATH DE number 1886324 (Why is no real title available?)
• scientific article; zbMATH DE number 1418340 (Why is no real title available?)
• A new dimension sensitive property for cellular automata
• Computational complexity of dynamical systems: the case of cellular automata
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Endomorphisms and automorphisms of the shift dynamical system
• Periodic points for onto cellular automata
• Reversibility and surjectivity problems of cellular automata
• Shifting and Lifting of Cellular Automata
• Solution of some conjectures about topological properties of linear cellular automata
• Topological Dynamics of 2D Cellular Automata

Cited in

(16)

• Characterization of two-dimensional cellular automata over ternary fields
• \(m\)-asynchronous cellular automata: from fairness to quasi-fairness
• Some Formal Properties of Asynchronous Cellular Automata
• Conservation of some dynamical properties for operations on cellular automata
• Sand automata as cellular automata
• On the undecidability of the limit behavior of cellular automata
• On the directional dynamics of additive cellular automata
• Non-uniform cellular automata: classes, dynamics, and decidability
• Non-uniform Cellular Automata
• Mathematical Foundations of Computer Science 2004
• From one-dimensional to two-dimensional cellular automata
• More decision algorithms for global properties of 1D cellular automata
• Asynchronous cellular automata and dynamical properties
• A family of sand automata
• Nondeterministic cellular automata
• Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues

This page was built for publication: Decidable Properties of 2D Cellular Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3533017)