Berthé, Valérie (ed.) et al., Combinatorics, automata, and number theory. Cambridge: Cambridge University Press (ISBN 978-0-521-51597-9/hbk). Encyclopedia of Mathematics and its Applications 135, 163-217 (2010).
Introduction: Given an infinite word, we can study the language of its finite factors. Intuitively, we expect that ‘simple’ words (because they are generated by simple devices, or have some regularity property) will also have a ‘simple’ language of factors. One way to quantify this is to just count factors of each length. In doing so, we associate a function with the infinite word considered: its factor complexity function.
This function was introduced in 1938 by G. A. Hedlund and M. Morse [Am. J. Math. 60, 815–866 (1938; Zbl 0019.33502)] under the name block growth as a tool to study symbolic dynamical systems. The name subword complexity was given in 1975 by Andrzej Ehrenfeucht, Kwok Pun Lee and Grzegorz Rozenberg. Here we use, factor complexity for consistence with the use of factor.
Factor complexity should not be confused with other notions of complexity, like algorithmic complexity or Kolmogorov complexity. We shall not use them here, and by ‘complexity’ we always mean ‘factor complexity’.