Example
\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\)
The morphism $\rho$ defined by $\rho(\sa{a})=\sa{ab}$,
$\rho(\sa{b})=\sa{ca}$ and $\rho(\sa{c})=\sa{bc}$ complies with the
conditions and produces the periodic word
$\rho^\infty(\sa{a})=\sa{abcabcabc}\cdots=(\sa{abc})^\infty$.
None of the letter is bispecial.
On the contrary, Fibonacci morphism $\phi$, defined by $\phi(\sa{a})=\sa{ab}$
and $\phi(\sa{b})=\sa{a}$, also satisfies the conditions but generates the
non-(ultimately) periodic Fibonacci word $\phi^\infty(\sa{a})=\sa{abaababa}\cdots$.
In it letter $\sa{a}$ is bispecial
since its occurrences are followed either by $\sa{a}$ or by $\sa{b}$, while
occurrences of letter $\sa{b}$ are all followed by $\sa{a}$.
|
Problem 89: Periodicity of morphic words
|
|
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.
