Behavior of various complexity functions
In this paper the author continues his study of pattern complexity. Let \(\mathbf{w}\) be an infinite word indexed by \(\mathbb{N} = \{ 0,1,2,\dots \}\). In block complexity (aka ``subword complexity or sometimes just ``complexity), we count the number of distinct factors of length \(n\) appearing in \(\mathbf{w}\). Maximal pattern complexity, by contrast, counts the maximal number of scattered (non-contiguous) subwords obtainable by fixing a set of offsets of cardinality \(n\), and ``sweeping it across \(\mathbf{w}\), counting the number of distinct words so obtained. Minimal pattern complexity is defined analogously. Here the author studies a generalization from infinite words to closed subsets \(\Omega\) of \(A^{\mathbb{N}}\), where \(A\) is a finite alphabet. (The original notions correspond to the case where \(\Omega\) is the orbit closure of an infinite word.) In particular he calls \(\Omega\) uniform if all three notions of complexity mentioned above coincide. A number of results are proved, including a characterization of block complexity, and inequalities for the case where \(\Omega\) is stationary and transitive. The paper suffers somewhat from language problems and could have benefited from editorial assistance. Reference [1] has now appeared: [\textit{S. Ferenczi} and \textit{P. Hubert}, RAIRO, Theor. Inform. Appl. 46, No. 1, 67--76 (2012; Zbl 1271.37012)].
- Factor complexity
- Three complexity functions
- On the complexity of infinite sequences
- On maximal pattern complexity of some automatic words
- Modified complexity and *-Sturmian word
- Drunken man infinite words complexity
- scientific article; zbMATH DE number 1992419
- Automata calculating the complexity of automatic sequences
- scientific article; zbMATH DE number 1992418
- Complexity of infinite sequences with zero entropy
- Combinatorial lemmas and applications to dynamics
- Language structure of pattern Sturmian words
- Maximal pattern complexity for discrete systems
- Maximal pattern complexity of two-dimensional words
- Maximal pattern complexity of words over \(\ell\) letters
- Maximal pattern complexity, dual system and pattern recognition
- On maximal pattern complexity of some automatic words
- Partitions by congruent sets and optimal positions
- Sequence entropy and the maximal pattern complexity of infinite words
- Substitutions in dynamics, arithmetics and combinatorics
- Super-stationary set, subword problem and the complexity
- Three complexity functions
- Uniform sets and complexity
- Uniform sets and super-stationary sets over general alphabets
- Uniform sets and complexity
- Super-stationary set, subword problem and the complexity
- Three complexity functions
- scientific article; zbMATH DE number 1124602 (Why is no real title available?)
- scientific article; zbMATH DE number 1979755 (Why is no real title available?)
- Complexity of leading digit sequences
- Central sets generated by uniformly recurrent words
- Maximal pattern complexity, dual system and pattern recognition
This page was built for publication: Behavior of various complexity functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764361)
