Periodicity of morphic words (Q2515198)

From MaRDI portal
Revision as of 13:35, 5 August 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Periodicity of morphic words
scientific article

    Statements

    Periodicity of morphic words (English)
    0 references
    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

    Identifiers