# zbMATH — the first resource for mathematics

On subword complexity of morphic sequences. (English) Zbl 1142.68464
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 146-157 (2008).
Summary: We sketch the proof of the following result: The subword complexity of an arbitrary morphic sequence is either $$\Theta(n^2)$$ or $$O(n ^{3/2})$$.
For the entire collection see [Zbl 1136.68005].

##### MSC:
 68R15 Combinatorics on words
Full Text: