Moscow Mathematical Journal

Volume 18, Issue 2, April–June 2018 pp. 211–303.

On Factor Complexity of Morphic Sequences

Authors: Rostislav Devyatov (1)
Author institution:(1) Department of Mathematics and Statistics, Faculty of Science, University of Ottawa, 585 King Edward, Ottawa, ON, K1N 6N5, Canada

Summary:

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 Θ(n^1+1/k) for some k∈ℕ, or is O(n log n).

2010 Math. Subj. Class. Primary: 68R15, 05A05; Secondary: 20M05.

Keywords: Morphic sequence, pure morphic sequence, factor complexity

Contents Full-Text PDF