PERIODICITY OF MORPHIC WORDS

Authors: Belov A.Y.¹, Mitrofanov I.V.², Allemand A.³
Affiliations:
1. Moscow Institute of Physics and Technology
3. Lomonosov Moscow State University
Issue: Vol 525, No 1 (2025)
Pages: 52-56
Section: MATHEMATICS
URL: https://ogarev-online.ru/2686-9543/article/view/356785
DOI: https://doi.org/10.7868/S3034504925050071
ID: 356785

Cite item

Full Text

Open Access
Restricted Access

Access granted
Restricted Access

Subscription Access

In this paper, we prove the decidability of the ultimate periodicity problem (the HD0L periodicity problem).

combinatorics of words, morphic sequence, HD0L-system, decidability

Moscow Institute of Physics and Technology

Moscow, Russia

Lomonosov Moscow State University

Moscow, Russia

Allouche J.-P. and Shallit J. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003.
Durand F. Decidability of the HD0L ultimate periodicity problem. arXiv:1111.3268v1 (2011).
Durand F. HD0L ω-equivalentc and periodicity problems in the primitive case (to the memory of G. Rauzy), accepted in J. of Uniform Distribution Theory.
Mitrofanov I. A proof for the decidability of HD0L ultimate periodicity. arXiv:1110.4780 (2011).
Митрофанов И.В. Периодичность морфических слов. Фундамент. и прикл. матем., 18:4 (2013), 107–119.
Mitrofanov I. On uniform recurrence of HD0L systems. arXiv:1111.1999 (2011).
Pansiot J.-J. Complexité des facteurs des mots infinis engendrés par morphismes itérés. In Proceedings of ICALP’84, volume 172 of Lecture Notes in Computer Science, pages 380–389. Springer-Verlag, 1984.
Nicolas F., Pritykin Y. On uniformly recurrent morphic sequences. International Journal of Foundations of Computer Science, Vol. 20, No. 5 (2009), 919–940.
Мучник А.А., Притыкин Ю.Л., Семенов А.Л. Последовательности, близкие к периодическим. УМН, 64:5(389) (2009), 21–96.

Supplementary Files

Action

1. JATS XML