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 substrings of n consecutive elements from the string u.
A Sturmian word is one of minimal complexity function n + 1. An example is the Fibonacci word.[1]
References
- ^ 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.