Decidability of the HD0L ultimate periodicity problem
Durand, Fabien
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013), p. 201-214 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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

Publié le : 2013-01-01
DOI : https://doi.org/10.1051/ita/2013035
Classification:  68Q45,  03B25 
@article{ITA_2013__47_2_201_0,
     author = {Durand, Fabien},
     title = {Decidability of the HD0L ultimate periodicity problem},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {47},
     year = {2013},
     pages = {201-214},
     doi = {10.1051/ita/2013035},
     mrnumber = {3072319},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2013__47_2_201_0}
}

Durand, Fabien. Decidability of the HD0L ultimate periodicity problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) pp. 201-214. doi : 10.1051/ita/2013035. http://gdmltest.u-ga.fr/item/ITA_2013__47_2_201_0/

[1] J.-P. Allouche, N. Rampersad and J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410 (2009) 2795-2803. | MR 2543333 | Zbl 1173.68044

[2] J.-P. Allouche and J.O. Shallit, Automatic Sequences, Theory, Applications, Generalizations. Cambridge University Press (2003). | MR 1997038 | Zbl 1086.11015

[3] J.P. Bell, E. Charlier, A.S. Fraenkel and M. Rigo, A decision problem for ultimately periodic sets in non-standard numeration systems. Internat. J. Algebra Comput. 9 (2009) 809-839. | Zbl 1194.68131

[4] J. Cassaigne and F. Nicolas, Quelques propriétés des mots substitutifs. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 661-676. | MR 2073019 | Zbl 1071.68086

[5] A. Cerný and J. Gruska, Modular trellises. The Book of L, edited by G. Rozenberg and A. Salomaa. Springer-Verlag (1986) 45-61. | Zbl 0586.68049

[6] A. Cobham, On the Hartmanis-Stearns problem for a class of tag machines. In IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory. Also appeared as IBM Research Technical Report RC-2178, August 23 (1968) 51-60.

[7] F. Durand, A characterization of substitutive sequences using return words. Discrete Math. 179 (1998) 89-101. | MR 1489074 | Zbl 0895.68087

[8] F. Durand, HD0L ω-equivalence and periodicity problems in the primitive case (To the memory of G. Rauzy). J. Unif. Distrib. Theory 7 (2012) 199-215. | MR 2943168 | Zbl pre06336934

[9] F. Durand and M. Rigo, Multidimensional extension of the Morse-Hedlund theorem. Eur. J. Comb. 34 (2013) 391-409. | MR 2994406 | Zbl pre06111989

[10] T. Harju and M. Linna, On the periodicity of morphisms on free monoids. RAIRO ITA 20 (1986) 47-54. | Numdam | MR 849965 | Zbl 0608.68065

[11] J. Honkala, A decision method for the recognizability of sets defined by number systems. RAIRO ITA 20 (1986) 395-403. | Numdam | MR 880843 | Zbl 0639.68074

[12] J. Honkala, Cancellation and periodicity properties of iterated morphisms. Theoret. Comput. Sci. 391 (2008) 61-64. | MR 2381352 | Zbl 1133.68037

[13] J. Honkala, On the simplification of infinite morphic words. Theoret. Comput. Sci. 410 (2009) 997-1000. | MR 2492043 | Zbl 1162.68031

[14] J. Honkala and M. Rigo, Decidability questions related to abstract numeration systems. Discrete Math. 285 (2004) 329-333. | MR 2062858 | Zbl 1076.68040

[15] R.A. Horn and C.R. Johnson, Matrix analysis. Cambridge University Press (1990). | MR 1084815 | Zbl 0704.15002

[16] P. Lecomte and M. Rigo, Abstract numeration systems. In Combinatorics, automata and number theory, Cambridge Univ. Press. Encyclopedia Math. Appl. 135 (2010) 108-162. | MR 2766741 | Zbl 1216.68147

[17] J. Leroux, A polynomial time presburger criterion and synthesis for number decision diagrams. In 20th IEEE Symposium on Logic In Computer Science (LICS 2005), IEEE Comput. Soc. (2005) 147-156.

[18] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995). | MR 1369092 | Zbl 1106.37301

[19] A. Maes and M. Rigo, More on generalized automatic sequences. J. Autom. Lang. Comb. 7 (2002) 351-376. | MR 1957696 | Zbl 1033.68069

[20] I. Mitrofanov, A proof for the decidability of HD0L ultimate periodicity. arXiv:1110.4780 (2011).

[21] A. Muchnik, The definable criterion for definability in Presburger arithmetic and its applications. Theoret. Comput. Sci. 290 (2003) 1433-1444. | MR 1937730 | Zbl 1052.68079

[22] J.-J. Pansiot, Hiérarchie et fermeture de certaines classes de tag-systèmes. Acta Informatica 20 (1983) 179-196. | MR 727164 | Zbl 0507.68046

[23] J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés. In ICALP84, Lect. Notes Comput. Sci. Vol. 172, edited by J. Paredaens. Springer-Verlag (1984) 380-389. | MR 784265 | Zbl 0554.68053

[24] J.-J. Pansiot, Decidability of periodicity for infinite words. RAIRO ITA 20 (1986) 43-46. | Numdam | MR 849964 | Zbl 0617.68063

[25] N. Priebe, Towards a characterization of self-similar tilings in terms of derived Voronoĭ tessellations. Geom. Dedicata 79 (2000) 239-265. | MR 1755727 | Zbl 1048.37014

[26] N. Priebe and B. Solomyak, Characterization of planar pseudo-self-similar tilings. Discrete Comput. Geom. 26 (2001) 289-306. | MR 1854103 | Zbl 0997.52012

[27] M. Queffélec, Substitution dynamical systems-spectral analysis. In Lect. Notes Math., Vol. 1294. Springer-Verlag (1987). | MR 924156 | Zbl 0642.28013

[28] O. Salon, Suites automatiques à multi-indices. In Séminaire de Théorie des Nombres de Bordeaux (1986-1987) 4.01-4.27. | Zbl 0653.10049

[29] O. Salon, Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris 305 (1987) 501-504. | MR 916320 | Zbl 0628.10007