PERIODICITY OF MORPHIC WORDS

Авторлар: Belov A.Y.¹, Mitrofanov I.V.², Allemand A.³
Мекемелер:
1. Moscow Institute of Physics and Technology
3. Lomonosov Moscow State University
Шығарылым: Том 525, № 1 (2025)
Беттер: 52-56
Бөлім: MATHEMATICS
URL: https://ogarev-online.ru/2686-9543/article/view/356785
DOI: https://doi.org/10.7868/S3034504925050071
ID: 356785

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат
Рұқсат жабық

Рұқсат берілді
Рұқсат жабық

Тек жазылушылар үшін

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.

Әрекет

1. JATS XML