Abstract:
The paper is devoted to an object well known in combinatorics of words, namely to so-called morphic sequences. The main goal of the paper is to solve (at least partially) the following question raised by J.-J. Pansiot in 1985: what can the factor complexity function of an arbitrary morphic sequence be?
We study structure of pure morphic and morphic sequences and prove the following result: the factor complexity of an arbitrary morphic sequence is either $\Theta(n^{1+1/k})$ for some $k\in\mathbb N$, or is $O(n\log n)$.
Key words and phrases:morphic sequence, pure morphic sequence, factor complexity.
Fulltext:
References