Computational complexity of dynamical systems: the case of cellular automata

DOI10.1016/j.ic.2008.03.012zbMath1154.68081MaRDI QIDQ948080

Pietro Di Lena, Luciano Margara

Publication date: 8 October 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.03.012

zbMATH Keywords

classification; cellular automata; universality

Mathematics Subject Classification ID

68Q80: Cellular automata (computational aspects)

37B15: Dynamical aspects of cellular automata

Related Items

Some Formal Properties of Asynchronous Cellular Automata, Conservation of some dynamical properties for operations on cellular automata, On the directional dynamics of additive cellular automata, Decidable Properties of 2D Cellular Automata, Non-uniform Cellular Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the measure attractor of a cellular automaton
• Zero-dimensional dynamical systems, formal languages, and universality
• Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms
• A theory of complexity for continuous time systems
• Subshifts of finite type and sofic systems
• Classes of linear automata
• Attractors in cellular automata
• Languages, equicontinuity and attractors in cellular automata
• An Introduction to Symbolic Dynamics and Coding
• Subshift attractors of cellular automata
• Endomorphisms and automorphisms of the shift dynamical system
• Simple Computation-Universal Cellular Spaces
• Machines, Computations, and Universality