Periodicity of morphic words (Q2515198): Difference between revisions

Given two alphabets (finite sets) \(A\) and \(B\), a morphism \(f\) of \(A^*\) (the free monoid generated by \(A\)) to itself admitting an iterative fixed point \(f^{\infty}(a)\) (with \(a \in A\)), and a morphism \(g\) from \(A^*\) to \(B^*\), is it decidable whether \(g(f^{\infty}(a))\) is ultimately periodic? The author proves that the answer is yes; the result was also proved independently by \textit{F. Durand} [RAIRO, Theor. Inform. Appl. 47, No. 2, 201--214 (2013; Zbl 1361.68112)]. The problem has a long history as recalled by the author (see the bibliography of the paper under review and that of the paper of F. Durand). But we would like to point out that a much more ancient paper, namely the paper by \textit{F. M. Dekking} in [Z. Wahrscheinlichkeitstheor. Verw. Geb. 41, 221--239 (1978; Zbl 0348.54034)] already contained the answer in the case of periodicity and pure morphic sequences (see Remarks (ii) and (iii) on page 226 of that paper). Also note that a simple proof for the case of automatic sequences (proved in [RAIRO, Inform. Théor. Appl. 20, 395--403 (1986; Zbl 0639.68074)] by \textit{J. Honkala}) was given in [\textit{J.-P. Allouche} et al., Theor. Comput. Sci. 410, No. 30--32, 2795--2803 (2009; Zbl 1173.68044)].