Complexity Through Nonextensivity
arXiv:physics/0103076 · doi:10.1016/S0378-4371(01)00444-7
Abstract
The problem of defining and studying complexity of a time series has interested people for years. In the context of dynamical systems, Grassberger has suggested that a slow approach of the entropy to its extensive asymptotic limit is a sign of complexity. We investigate this idea further by information theoretic and statistical mechanics techniques and show that these arguments can be made precise, and that they generalize many previous approaches to complexity, in particular unifying ideas from the physics literature with ideas from learning and coding theory; there are even connections of this statistical approach to algorithmic or Kolmogorov complexity. Moreover, a set of simple axioms similar to those used by Shannon in his development of information theory allows us to prove that the divergent part of the subextensive component of the entropy is a unique complexity measure. We classify time series by their complexities and demonstrate that beyond the `logarithmic' complexity classes widely anticipated in the literature there are qualitatively more complex, `power--law' classes which deserve more attention.
summarizes and extends physics/0007070
References in corpus (2)
Cited by in corpus (23)
- JIDT: An information-theoretic toolkit for studying the dynamics of complex systems
- The Organization of Intrinsic Computation: Complexity-Entropy Diagrams and the Diversity of Natural Information Processing
- A framework for the local information dynamics of distributed computation in complex systems
- Identification of functional information subgraphs in complex networks
- Assessing the Significance of Directed and Multivariate Measures of Linear Dependence Between Time Series
- On the Vocabulary of Grammar-Based Codes and the Logical Consistency of Texts
- Network Analysis of the State Space of Discrete Dynamical Systems
- Excess entropy in natural language: present state and perspectives
- Characterising information-theoretic storage and transfer in continuous time processes
- Is Natural Language a Perigraphic Process? The Theorem about Facts and Words Revisited
- On Hidden Markov Processes with Infinite Excess Entropy
- Towards a Universal Measure of Complexity
- Statistical data assimilation for estimating electrophysiology simultaneously with connectivity within a biological neuronal network
- Breakdown of random matrix universality in Markov models
- A Note on A Priori Forecasting and Simplicity Bias in Time Series
- Natural Complexity, Computational Complexity and Depth
- Complex Network Analysis of State Spaces for Random Boolean Networks
- Predictive information in a nonequilibrium critical model
- Extrinsic vs Intrinsic Criticality in Systems with Many Components
- A Preadapted Universal Switch Distribution for Testing Hilberg's Conjecture
- Intrinsic computation of a Monod-Wyman-Changeux molecule
- Entangled criticality and irreversibility in random Markov dynamics
- Complexity measures and occurrence of the breaking point in the neutron and gamma-rays time series measured with organic scintillators