×

Periodicity of morphic words. (English. Russian original) Zbl 1385.68028

J. Math. Sci., New York 206, No. 6, 679-687 (2015); translation from Fundam. Prikl. Mat. 18, No. 4, 107-119 (2013).
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 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 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 J. Honkala) was given in [J.-P. Allouche et al., Theor. Comput. Sci. 410, No. 30–32, 2795–2803 (2009; Zbl 1173.68044)].

MSC:

68R15 Combinatorics on words
11B85 Automata sequences
Full Text: DOI

References:

[1] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge Univ. Press, Cambridge (2003). · Zbl 1086.11015 · doi:10.1017/CBO9780511546563
[2] F. Durand, Decidability of the HD0L Ultimate Periodicity Problem, arXiv:1111.3268v1 (2011). · Zbl 1361.68112
[3] F. Durand, “HD0L <Emphasis Type=”Italic“>ω-equivalence and periodicity problems in the primitive case (to the memory of G. Rauzy),” J. Unif. Distrib. Theory, to appear. · Zbl 1313.68067
[4] A. Ehrenfeucht and G. Rozenberg, “Repetition of subwords in DOL languages,” J. Inform. Control, 59, No. 1-3, 13-35 (1983). · Zbl 0549.68076 · doi:10.1016/S0019-9958(83)80028-X
[5] T. Harju and M. Linna, “On the periodicity of morphisms on free monoid,” Inform. Théor. Appl., 20, No. 1, 47-54 (1986). · Zbl 0608.68065
[6] J. Honkala, “A decision method for the recognizability of sets defined by number systems,” Inform. Th´eor. Appl., 20, No. 4, 395-403 (1986). · Zbl 0639.68074
[7] J. Honkala and M. Rigo, “Decidability questions related to abstract numeration systems,” Discrete Math., 285, No. 1-3, 329-333 (2004). · Zbl 1076.68040 · doi:10.1016/j.disc.2004.05.004
[8] A. Kanel-Belov and I. Mitrofanov, Periodicity of Rauzy Scheme and Substitutional Systems, arXiv:1107.0185 [math.DS] (2011). · Zbl 0549.68076
[9] I. Mitrofanov, A Proof for the Decidability of HD0L Ultimate Periodicity, arXiv:1110.4780 (2011). · Zbl 0554.68053
[10] An. A. Muchnik, Yu. L. Pritykin, and A. L. Semenov, “Sequences close to periodic,” Usp. Mat. Nauk, 64, No. 5, 21-96 (2009). · Zbl 1208.03017 · doi:10.4213/rm9315
[11] F. Nicolas and Yu. Pritykin, “On uniformly recurrent morphic sequences,” Int. J. Found. Comput. Sci., 20, No. 5, 919-940 (2009). · Zbl 1187.68368 · doi:10.1142/S0129054109006966
[12] Pansiot, J-J, Complexité des facteurs des mots infinis engendrés par morphismes itérés, No. 172, 380-389 (1984), Berlin · Zbl 0554.68053
[13] J.-J. Pansiot, “Decidability of periodicity for infinite words,” Inform. Théor. Appl., 20, No. 1, 43-46 (1986). · Zbl 0617.68063
[14] M. Rigo and A. Maes, “More on generalized automatic sequences,” J. Autom. Lang. Comb., 7, No. 3, 351-376 (2002). · Zbl 1033.68069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.