Tim Smith - A Characterization of Morphic Words with Polynomial Growth

dmtcs:5324 - Discrete Mathematics & Theoretical Computer Science, February 6, 2020, vol. 22 no. 1 - https://doi.org/10.23638/DMTCS-22-1-3
A Characterization of Morphic Words with Polynomial GrowthArticle

Authors: Tim Smith

    A morphic word is obtained by iterating a morphism to generate an infinite word, and then applying a coding. We characterize morphic words with polynomial growth in terms of a new type of infinite word called a $\textit{zigzag word}$. A zigzag word is represented by an initial string, followed by a finite list of terms, each of which repeats for each $n \geq 1$ in one of three ways: it grows forward [$t(1)\ t(2)\ \dotsm\ t(n)]$, backward [$t(n)\ \dotsm\ t(2)\ t(1)$], or just occurs once [$t$]. Each term can recursively contain subterms with their own forward and backward repetitions. We show that an infinite word is morphic with growth $\Theta(n^k)$ iff it is a zigzag word of depth $k$. As corollaries, we obtain that the morphic words with growth $O(n)$ are exactly the ultimately periodic words, and the morphic words with growth $O(n^2)$ are exactly the multilinear words.


    Volume: vol. 22 no. 1
    Section: Automata, Logic and Semantics
    Published on: February 6, 2020
    Accepted on: December 1, 2019
    Submitted on: March 29, 2019
    Keywords: Computer Science - Formal Languages and Automata Theory

    Consultation statistics

    This page has been seen 1279 times.
    This article's PDF has been downloaded 309 times.