PERIODICITY OF MORPHIC WORDS

Autores: Belov A.Y.¹, Mitrofanov I.V.², Allemand A.³
Afiliações:
1. Moscow Institute of Physics and Technology
3. Lomonosov Moscow State University
Edição: Volume 525, Nº 1 (2025)
Páginas: 52-56
Seção: MATHEMATICS
URL: https://ogarev-online.ru/2686-9543/article/view/356785
DOI: https://doi.org/10.7868/S3034504925050071
ID: 356785

Citar

Texto integral

Acesso aberto
Acesso é fechado

Acesso está concedido
Acesso é fechado

Somente assinantes

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.

Ação

1. JATS XML