On Subword Complexity of Morphic Sequences

Abstract

We study structure of pure morphic and morphic sequences and prove the following result: the subword complexity of arbitrary morphic sequence is either $\Theta (n^{1+1/k})$ for some $k\in \mathbb{N}$, or is $O(n\log n)$.

61 pages, 5 figures