Complexity of sequences and dynamical systems
From MaRDI portal
The paper surveys results of recent papers on the combinatorial notion of symbolic complexity. In particular, the author gives a survey of an open question which is still very much in progress, namely, to determine which function can be the symbolic complexity function of a sequence. Also the links between the complexity of a sequence and its associated dynamical system are investigated and it is insisted on the cases where the knowledge of the complexity function allows to know either the sequence or at least the system. This leads to another open question, \(S\)-adic conjecture, and to a conceptual link with the notion of Kolmogorov-Chaitin complexity for infinite sequences, which is discussed.
Recommendations
Cited in
(80)- Asymptotic subword complexity of fixed points of group substitutions
- Uniform sets and complexity
- Complexity for finite factors of infinite sequences
- Some characteristics of complex behavior of orbits in dynamical systems
- Arithmetical complexity of symmetric D0L words.
- An algorithm for the word entropy
- Polynomial entropy and expansivity
- An extension of the periodicity lemma to longer periods
- Palindrome complexity.
- Universal \(\beta\)-expansions
- The complexity of generalized Sturmian sequences
- Subword complexity and power avoidance
- The subword complexity of a class of infinite binary words
- Substitution dynamical systems on infinite alphabets
- On the arithmetical complexity of Sturmian words
- Quasiperiodic and Lyndon episturmian words
- Dynamic modularity in discrete-time models of regulatory networks
- On periodicity and low complexity of infinite permutations
- On a class of infinite words with affine factor complexity
- Mirror substitutions and palindromic sequences
- On the subword complexity of Thue-Morse polynomial extractions
- Language structure of pattern Sturmian words
- Internal shortest absent word queries in constant time and linear space
- The easily bored sequence
- Growth of étale groupoids and simple algebras
- Lamination languages
- Generalized Hausdorff dimensions of sets of real numbers with zero entropy expansion
- Three complexity functions
- Orbit equivalent substitution dynamical systems and complexity
- Sequences With High Nonlinear Complexity
- On maximal pattern complexity of some automatic words
- Invariant measures for Cantor dynamical systems
- On possible growths of arithmetical complexity
- Sequences of low arithmetical complexity
- Drunken man infinite words complexity
- Sequences close to periodic
- Constructing Infinite Words of Intermediate Arithmetical Complexity
- Directive words of episturmian words: equivalences and normalization
- COMPLEXITY OF CONTINUOUS SEMI-FLOWS AND RELATED DYNAMICAL PROPERTIES
- ON UNIFORMLY RECURRENT MORPHIC SEQUENCES
- Complexity of sequences with values in a finite set: some examples
- Constructing partial words with subword complexities not achievable by full words
- scientific article; zbMATH DE number 1157222 (Why is no real title available?)
- Hereditary properties of words
- Rank and symbolic complexity
- Algorithmic combinatorics on partial words
- Symbolic dynamics for non-uniformly hyperbolic systems
- Complexity of leading digit sequences
- Two infinite words with cubic subword complexity
- On the computational complexity of the Arnold complexity of binary words
- Entropy ratio for infinite sequences with positive entropy
- Complexity and fractal dimensions for infinite sequences with positive entropy
- Episturmian words: a survey
- On minimal Sturmian partial words
- Combinatorics of past-similarity in higher dimensional transition systems
- On possible growths of Toeplitz languages
- On the transition semigroups of centrally labeled Rauzy graphs.
- Infinite permutations of lowest maximal pattern complexity
- SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS
- The complexity of Fibonacci-like kneading sequences
- Sequences of linear arithmetical complexity
- Space–time complexity in Hamiltonian dynamics
- Sequential dynamical systems over words
- Double sequences of low complexity
- Bracket words: A generalisation of Sturmian words arising from generalised polynomials
- Gaps and approximations in the space of growth functions
- On the structure of generic subshifts
- Frequency-constrained substring complexity
- On word complexity and topological entropy of random substitution subshifts
- On the fragmentary complexity of symbolic sequences
- Opacity complexity of automatic sequences: the general case
- A Pansiot-type subword complexity theorem for automorphisms of free groups
- The reflection complexity of sequences over finite alphabets
- Subproduct systems and Cartesian systems: new results on factorial languages and their relations with other areas
- Subword complexity of uniform D0L words over finite groups
- On the complexity of a family of \(k\)-context-free sequences
- On the joint subword complexity of automatic sequences
- Quasiperiodic Sturmian words and morphisms
- Complexity for extended dynamical systems
- On complexity functions of infinite words associated with generalized Dyck languages
This page was built for publication: Complexity of sequences and dynamical systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1304818)
