On Subword Complexity of Morphic Sequences

DOI10.1007/978-3-540-79709-8_17MaRDI QIDQ3503634zbMATH OpenOpenAlexFDO

Authors Rostislav Deviatov

Publication date 5 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.02310

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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 $kinmathbbN$, or is $O(nlogn)$.

Cited in

(13)

• On the asymptotic abelian complexity of morphic words
• On the structure of compacted subword graphs of Thue-Morse words and their applications
• On the joint subword complexity of automatic sequences
• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
• Factor complexity and permutation complexity of the generalized Morse sequence
• On the permutation complexity of the Cantor-like sequences
• The reflection complexity of sequences over finite alphabets
• Subword complexity and Laurent series
• scientific article; zbMATH DE number 5074393 (Why is no real title available?)
• Extremal words in morphic subshifts
• Subword complexity and periodicity in two or more dimensions
• The number of primitive words of unbounded exponent in the language of an HD0L-system is finite
• scientific article; zbMATH DE number 5990082 (Why is no real title available?)

This page was built for publication: On Subword Complexity of Morphic Sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503634)