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] , and , Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410 (2009) 2795-2803. | MR | Zbl
[2] and , Automatic Sequences, Theory, Applications, Generalizations. Cambridge University Press (2003). | MR | Zbl
[3] , , and , A decision problem for ultimately periodic sets in non-standard numeration systems. Internat. J. Algebra Comput. 9 (2009) 809-839. | Zbl
[4] and , Quelques propriétés des mots substitutifs. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 661-676. | MR | Zbl
[5] and , Modular trellises. The Book of L, edited by G. Rozenberg and A. Salomaa. Springer-Verlag (1986) 45-61. | Zbl
[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] and , Multidimensional extension of the Morse-Hedlund theorem. Eur. J. Comb. 34 (2013) 391-409. | MR
[10] and , On the periodicity of morphisms on free monoids. RAIRO ITA 20 (1986) 47-54. | Numdam | MR | Zbl
[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] and , Decidability questions related to abstract numeration systems. Discrete Math. 285 (2004) 329-333. | MR | Zbl
[15] and , Matrix analysis. Cambridge University Press (1990). | MR | Zbl
[16] and , Abstract numeration systems. In Combinatorics, automata and number theory, Cambridge Univ. Press. Encyclopedia Math. Appl. 135 (2010) 108-162. | MR | Zbl
[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] and , An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995). | MR | Zbl
[19] and , More on generalized automatic sequences. J. Autom. Lang. Comb. 7 (2002) 351-376. | MR | Zbl
[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] and , Characterization of planar pseudo-self-similar tilings. Discrete Comput. Geom. 26 (2001) 289-306. | MR | Zbl
[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 :
