On Subword Complexity of Morphic Sequences

2015/02/08 by Rostislav Devyatov, Devyatov, Rostislav · 1 citation
Computer Science · #68R15 #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1502.02310

openalex publication_date 2015/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Cited by

• Decidability of the isomorphism and the factorization between minimal substitution subshifts

Related

• On the subword complexity of the fixed point of a → aab, b → b, and generalizations
• On the shape of subword complexity sequences of finite words
• Maximum order complexity of the sum of digits function in Zeckendorf\n base and polynomial subsequences
• A Taxonomy of Morphic Sequences
• Complexity of Substitutive Sequences - Calculation of the Complexities of Substitutive Sequences Over a Binary Alphabet