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 3540441417.