CLR cover
Previous problem

Problem 89: Periodicity of morphic words

Next problem

The problem shows that it is possible to test whether an infinite word generated by a (finite) morphism is periodic.

An infinite morphic word is obtained by iterating a morphism $\theta$ from $A^+$ to itself, where $A=\{\sa{a}, \sa{b}, \dots\}$ is a finite alphabet. To do so, we assume that $\theta$ is prolongable over the letter $\sa{a}$, that is, $\theta(\sa{a}) = \sa{a}u$ for $u\in A^+$. Then $\Theta=\theta^\infty(\sa{a})$ exists and is $\sa{a}u\theta(u)\theta^2(u)\cdots$. The infinite word $\Theta$ is a fixed point of $\theta$, that is, $\theta(\Theta)=\Theta$.

The infinite word $\Theta$ is periodic if it can be written $z^\infty$ for some (finite) words $z$, $z\neq \varepsilon$.

To avoid unnecessary complications we assume that the morphism $\theta$ is both irreducible, which means that any letter is accessible from any letter (for any $c,d\in A$ the letter $d$ appears in $\theta^k(c)$ for some integer $k$), and is elementary, which means it is not the product $\eta \circ \zeta$ of two morphisms $\zeta:A^+ \longrightarrow B^+$ and $\eta:B^+ \longrightarrow A^+$, where $B$ is an alphabet smaller than $A$. The second condition implies that $\theta$ is injective on $A^*$ and on $A^\infty$.

For an irreducible and elementary morphism $\theta$ prolongable over letter $\sa{a}$, design an algorithm that checks if $\Theta=\theta^{\infty}(\sa{a})$ is periodic and that runs in time $O(\Sigma\{|\theta(b)| \mid b\in A\})$.
$\Theta$ is periodic if and only if it has no bispecial letter, that is, occurrences of each letter in $\Theta$ are all followed by a unique letter.

References

  • J. Almeida, A. Costa, R. Kyriakoglou, and D. Perrin. Profinite Semigroups and Symbolic Dynamics, volume 2274 of Lecture Notes in Mathematics. Springer, 2020.
  • P. Kurka. Topological and Symbolic Dynamics. Société Mathématique de France, 2003.
  • J. Pansiot. Decidability of periodicity for infinite words. ITA, 20(1):43-46, 1986.
  • G. Rozenberg and A. Salomaa. The Mathematical Theory of L Systems. Academic Press, 1980.