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://journals.rcsi.science/2686-9543/article/view/356785
DOI: https://doi.org/10.7868/S3034504925050071
ID: 356785

如何引用文章

全文:

开放存取

##reader.subscriptionAccessGranted##
受限制的访问

订阅存取

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