Decidability of the HD0L ultimate periodicity problem
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 2, pp. 201-214.

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

DOI : 10.1051/ita/2013035
Classification : 68Q45, 03B25
Mots-clés : HD0L - periodicity - decidability - return words 
@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},
     pages = {201--214},
     publisher = {EDP-Sciences},
     volume = {47},
     number = {2},
     year = {2013},
     doi = {10.1051/ita/2013035},
     mrnumber = {3072319},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2013035/}
}
TY  - JOUR
AU  - Durand, Fabien
TI  - Decidability of the HD0L ultimate periodicity problem
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2013
SP  - 201
EP  - 214
VL  - 47
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2013035/
DO  - 10.1051/ita/2013035
LA  - en
ID  - ITA_2013__47_2_201_0
ER  - 
%0 Journal Article
%A Durand, Fabien
%T Decidability of the HD0L ultimate periodicity problem
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2013
%P 201-214
%V 47
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2013035/
%R 10.1051/ita/2013035
%G en
%F 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) no. 2, pp. 201-214. doi : 10.1051/ita/2013035. http://www.numdam.org/articles/10.1051/ita/2013035/

[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 | Zbl

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

[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

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

[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

[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 | Zbl

[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

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

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

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

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

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

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

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

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

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

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

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

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

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

Cité par Sources :