Lempel-Ziv complexity analysis of one dimensional cellular automata
From MaRDI portal
Publication:4591802
DOI10.1063/1.4936876zbMATH Open1374.37020arXiv1511.08657OpenAlexW2176519179WikidataQ87001420 ScholiaQ87001420MaRDI QIDQ4591802FDOQ4591802
Authors: E. Estevez-Rams, R. Lora-Serrano, C. A. J. Nunes, B. Aragón Fernández 
Publication date: 17 November 2017
Published in: Chaos: An Interdisciplinary Journal of Nonlinear Science (Search for Journal in Brave)
Abstract: Cellular automata (CA) have long attracted attention as dynamical systems with local updating rules and yet can exhibit, for certain rules, complex, long space and time correlated patterns. This contrast with other rules which results in trivial patterns being homogeneous or periodic. In this article we approach CA from two related angles: we analyze the information transfer in the time evolution of CA driven sequences and; we revisit the sensibility of the initial configuration on sequence evolution. In order to do so, we borrow a recently reported information distance based on Kolmogorov algorithmic complexity. The normalized information distance has been used previously to find a hierarchical clustering of CA rules. What is different in our approach, is the temporal analysis of the sequence evolutions by correlating different calculated distances with entropy density. Entropy rate, is a length invariant measure of the amount of irreducible randomness in a dynamical process. In order to perform our analysis, we incorporate to the practical calculation of the entropy rate and the distance measure, the use of Lempel-Ziv complexity. Lempel-Ziv complexity carries a number of practical advantages while avoiding the uncomputable nature of Kolmogorov randomness. The reduction of entropy density during time evolution can be related to energy dissipation through Landauer principle. Related to the last fact, is the computational capabilities of CA as information processing rules, were the performed analysis could be used to select CA rules amiable for simulating different physical process. The tools developed in this article for the analysis of the CA are easily extendible to the study of other one dimensional dynamical systems.
Full work available at URL: https://arxiv.org/abs/1511.08657
Recommendations
Cites Work
- Elements of Information Theory
- Theory of cellular automata: a survey
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Compression-based investigation of the dynamical properties of cellular automata and other systems
- Irreversibility and Heat Generation in the Computing Process
- The Similarity Metric
- Title not available (Why is that?)
- Kolmogorov complexity and cellular automata classification
- On the Complexity of Finite Sequences
- Title not available (Why is that?)
- Normalized Lempel-Ziv complexity and its application in bio-sequence analysis
- Lyapunov exponents for one-dimensional cellular automata
- Coding theorems for individual sequences
- Upper bound on the products of particle interactions in cellular automata
- A sequential algorithm for the universal coding of finite memory sources
- Variance estimators for the Lempel-Ziv entropy rate estimator
- Quantifying complexity in the minority game
Cited In (7)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Phenomenology of coupled nonlinear oscillators
- Information density, structure and entropy in equilibrium and non-equilibrium systems
- Computational capabilities at the edge of chaos for one dimensional systems undergoing continuous transitions
- Correlation and collective behaviour in Adler-type locally coupled oscillators at the edge of chaos
This page was built for publication: Lempel-Ziv complexity analysis of one dimensional cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4591802)
