Kolmogorov complexity and cellular automata classification

DOI10.1016/S0304-3975(00)00012-8zbMath0973.68088OpenAlexW2046142610MaRDI QIDQ5941280

J.-C. Dubacq, Enrico Formenti, Bruno Durand

Publication date: 20 August 2001

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00012-8

zbMATH Keywords

cellular automataalgorithmic complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Cellular automata (computational aspects) (68Q80)

Related Items (7)

Exploring programmable self-assembly in non-DNA based molecular computing ⋮ Progress, gaps and obstacles in the classification of cellular automata ⋮ Lempel-Ziv complexity analysis of one dimensional cellular automata ⋮ Classifying 1D elementary cellular automata with the 0-1 test for chaos ⋮ Fourier transform bounded Kolmogorov complexity ⋮ Computational capabilities at the edge of chaos for one dimensional systems undergoing continuous transitions ⋮ Some results about the chaotic behavior of cellular automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pattern growth in elementary cellular automata
• Topological and measure-theoretic properties of one-dimensional cellular automata
• Computation theory of cellular automata
• Rice's theorem for the limit sets of cellular automata
• Can an individual sequence of zeros and ones be random?
• Attractors in cellular automata
• On Devaney's Definition of Chaos
• Chaos Without Nonperiodicity
• Languages, equicontinuity and attractors in cellular automata
• Relations between varieties of kolmogorov complexities
• Endomorphisms and automorphisms of the shift dynamical system
• Complexity oscillations in infinite binary sequences
• The definition of random sequences

This page was built for publication: Kolmogorov complexity and cellular automata classification