Complexity function
In computer science, the complexity function of a string, a finite or infinite sequence u of letters from some alphabet, is the function pu(n) of a positive integer n that counts the number of different factors (consecutive substrings) of length n from the string u.[1][2][3]
For a string u of length at least n over an alphabet of size k we clearly have
the bounds being achieved by the constant word and, for example, the Champernowne word respectively.[4] For infinite words u, we have pu(n) bounded if u is ultimately periodic (a finite, possibly empty, sequence followed by a finite cycle). Conversely, if pu(n) ≤ n for some n, then u is ultimately periodic.[3]
An aperiodic sequence is one which is not ultimately periodic. An aperiodic sequence has strictly increasing complexity function,[5] so p(n) is at least n+1.[6]
A set S of finite binary words is balanced if for each n the subset Sn of words of length n has the property that the Hamming weight of the words in Sn takes at most two distinct values. A balanced sequence is one for which the set of factors is balanced. A balanced sequence has complexity sequence at most n+1.[7]
A Sturmian word is one with complexity function n + 1.[8] A sequence is Sturmian if and only if it is balanced and aperiodic.[2] An example is the Fibonacci word.[8][9]
The topological entropy of an infinite sequence u is defined by
The limit exists as the logarithm of the complexity function is subadditive.[10]
References
- ^ Lothaire (2011) p.7
- ^ a b Lothaire (2011) p.46
- ^ a b Pytheas Fogg (2002) p.3
- ^ Cassaigne & Nicolas (2010) p.165
- ^ Cassaigne & Nicolas (2010) p.166
- ^ Lothaire (2011) p.22
- ^ Lothaire (2011) p.48
- ^ a b Pytheas Fogg (2002) p.6
- ^ de Luca, Aldo (1995). "A division property of the Fibonacci word". Information Processing Letters. 54 (6): 307–312. doi:10.1016/0020-0190(95)00067-M.
- ^ Pytheas Fogg (2002) p.4
- Cassaigne, J.; Nicolas, F. (2010). "Factor complexity". In Berthé, Valérie; Rigo, Michel (eds.). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge: Cambridge University Press. pp. 163–247. ISBN 978-0-521-51597-9. Zbl 1216.68204.
- Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.
- Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.