Smith, Tim - A Characterization of Morphic Words with Polynomial Growth

dmtcs:5324 - Discrete Mathematics & Theoretical Computer Science, February 6, 2020, vol. 22 no. 1
A Characterization of Morphic Words with Polynomial Growth

Authors: Smith, Tim

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
Submitted on: March 29, 2019
Keywords: Computer Science - Formal Languages and Automata Theory


Share