×

zbMATH — the first resource for mathematics

On subword complexity of morphic sequences. (English) Zbl 1142.68464
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 146-157 (2008).
Summary: We sketch the proof of the following result: The subword complexity of an arbitrary morphic sequence is either \(\Theta(n^2)\) or \(O(n ^{3/2})\).
For the entire collection see [Zbl 1136.68005].

MSC:
68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI