Periodicity of morphic words (Q2515198)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Periodicity of morphic words |
scientific article |
Statements
Periodicity of morphic words (English)
0 references
31 July 2015
0 references
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)].
0 references
morphic sequences
0 references
ultimate periodicity
0 references
decidability
0 references