CLR cover
Previous problem

Problem 68: Searching an Infinite Word

Next problem
\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \)

The goal is to design an algorithm for matching a pattern in an infinite word. Since there is no answer for general infinite words, we restrict the question to a pure morphic word. It is an infinite word 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 $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$, i.e. $\theta(\Theta)=\Theta$.

To avoid trivial cases, like that of the morphism $\eta$ defined by $\eta(\sa{a})=\sa{ab}$, $\eta(\sa{b})=\sa{c}$, $\eta(\sa{c})=\sa{b}$ and $\eta(\sa{d})=\sa{d}$ where the letter $\sa{d}$ is useless and the letter $\sa{a}$ appear only once in $\Theta$, we assume that $\theta$ is irreducible. It means that any letter is accessible from any letter: for any distinct letter $c,d\in A$ the letter $d$ appears in $\theta^k(c)$ for some integer $k$.

The Thue-Morse morphism $\mu$ and Fibonacci morphism $\phi$ (see Remarkable Words) are both irreducible morphisms.

Show how to test if a morphism is irreducible.

Design an algorithm to compute the set of factors of length $m$ occurring in the infinite word $\Theta=\theta^\infty(\sa{a})$, where $\theta$ is an irreducible morphism.

When the set of length-$m$ factors of $\Theta$ is represented by a (deterministic) trie, testing if a pattern of length $m$ appears in $\Theta$ becomes a mere top-down traversal of the trie.

References

  • F. Durand and J. Leroy. The constant of recognizability is computable for primitive morphisms. CoRR, abs/1610.05577, 2016.