Navigation: Home > Publications > Preprint: On Factor Complexity of Morphic Sequences

Preprint: R. Devyatov, On Factor Complexity of Morphic Sequences

Abstract
The paper is devoted to an object well known in combinatorcs 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 Θ(n1+1/k) for some kN, or is O(n log n).
Version 10: download pdf; download zip archive with all sources
This is last available version.
Version 4: download pdf; download zip archive with all sources
This is the version available on arXiv, as arXiv:1502.02310v1.