In this paper we prove the decidability of the HD0L ultimate periodicity problem.
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2013035/
[1] Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410 (2009) 2795-2803. | MR | Zbl
, and ,[2] Automatic Sequences, Theory, Applications, Generalizations. Cambridge University Press (2003). | MR | Zbl
and ,[3] A decision problem for ultimately periodic sets in non-standard numeration systems. Internat. J. Algebra Comput. 9 (2009) 809-839. | Zbl
, , and ,[4] Quelques propriétés des mots substitutifs. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 661-676. | MR | Zbl
and ,[5] Modular trellises. The Book of L, edited by G. Rozenberg and A. Salomaa. Springer-Verlag (1986) 45-61. | Zbl
and ,[6] 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] A characterization of substitutive sequences using return words. Discrete Math. 179 (1998) 89-101. | MR | Zbl
,[8] 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] Multidimensional extension of the Morse-Hedlund theorem. Eur. J. Comb. 34 (2013) 391-409. | MR
and ,[10] On the periodicity of morphisms on free monoids. RAIRO ITA 20 (1986) 47-54. | Numdam | MR | Zbl
and ,[11] A decision method for the recognizability of sets defined by number systems. RAIRO ITA 20 (1986) 395-403. | Numdam | MR | Zbl
,[12] Cancellation and periodicity properties of iterated morphisms. Theoret. Comput. Sci. 391 (2008) 61-64. | MR | Zbl
,[13] On the simplification of infinite morphic words. Theoret. Comput. Sci. 410 (2009) 997-1000. | MR | Zbl
,[14] Decidability questions related to abstract numeration systems. Discrete Math. 285 (2004) 329-333. | MR | Zbl
and ,[15] Matrix analysis. Cambridge University Press (1990). | MR | Zbl
and ,[16] Abstract numeration systems. In Combinatorics, automata and number theory, Cambridge Univ. Press. Encyclopedia Math. Appl. 135 (2010) 108-162. | MR | Zbl
and ,[17] 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] An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995). | MR | Zbl
and ,[19] More on generalized automatic sequences. J. Autom. Lang. Comb. 7 (2002) 351-376. | MR | Zbl
and ,[20] A proof for the decidability of HD0L ultimate periodicity. arXiv:1110.4780 (2011).
,[21] The definable criterion for definability in Presburger arithmetic and its applications. Theoret. Comput. Sci. 290 (2003) 1433-1444. | MR | Zbl
,[22] Hiérarchie et fermeture de certaines classes de tag-systèmes. Acta Informatica 20 (1983) 179-196. | MR | Zbl
,[23] 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] Decidability of periodicity for infinite words. RAIRO ITA 20 (1986) 43-46. | Numdam | MR | Zbl
,[25] Towards a characterization of self-similar tilings in terms of derived Voronoĭ tessellations. Geom. Dedicata 79 (2000) 239-265. | MR | Zbl
,[26] Characterization of planar pseudo-self-similar tilings. Discrete Comput. Geom. 26 (2001) 289-306. | MR | Zbl
and ,[27] Substitution dynamical systems-spectral analysis. In Lect. Notes Math., Vol. 1294. Springer-Verlag (1987). | MR | Zbl
,[28] Suites automatiques à multi-indices. In Séminaire de Théorie des Nombres de Bordeaux (1986-1987) 4.01-4.27. | Zbl
,[29] Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris 305 (1987) 501-504. | MR | Zbl
,Cité par Sources :