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 of a positive integer n that counts the number of different factors (consecutive substrings) of length n from the string u.

An aperiodic sequence is one which does not consist of a finite sequence followed by a finite cycle. An aperiodic sequence has complexity function at least n+1.^[1]

A set S of finite binary words is balanced if for each n the subset S_n of words of length n has the property that the Hamming weight of the words in S_n 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.^[2]

A Sturmian word is one of minimal complexity function n + 1. A sequence is Sturmian if and only if it is balanced and aperiodic.^[3] An example is the Fibonacci word.^[4]

References

1. Lothaire (2011) p.22
2. Lothaire (2011) p.48
3. Lothaire (2011) p.46
4. 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.

• Fogg, N. Pytheas; Berthé, Valérie, eds. (2002). Substitutions in dynamics, arithmetics, and combinatorics. Lecture notes in mathematics. Vol. 1794. Springer. ISBN 3-540-44141-7.
• 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.