Decidability of the HD0L ultimate periodicity problem

 Access to full text

1. [1] J.-P. Allouche, N. Rampersad and J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci.410 (2009) 2795–2803. Zbl1173.68044MR2543333
2. [2] J.-P. Allouche and J.O. Shallit, Automatic Sequences, Theory, Applications, Generalizations. Cambridge University Press (2003). Zbl1086.11015MR1997038
3. [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. Zbl1194.68131
4. [4] J. Cassaigne and F. Nicolas, Quelques propriétés des mots substitutifs. Bull. Belg. Math. Soc. Simon Stevin10 (2003) 661–676. Zbl1071.68086MR2073019
5. [5] A. Cerný and J. Gruska, Modular trellises. The Book of L, edited by G. Rozenberg and A. Salomaa. Springer-Verlag (1986) 45–61. Zbl0586.68049
6. [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. [7] F. Durand, A characterization of substitutive sequences using return words. Discrete Math.179 (1998) 89–101. Zbl0895.68087MR1489074
8. [8] F. Durand, HD0L ω-equivalence and periodicity problems in the primitive case (To the memory of G. Rauzy). J. Unif. Distrib. Theory7 (2012) 199–215. Zbl1313.68067MR2943168
9. [9] F. Durand and M. Rigo, Multidimensional extension of the Morse-Hedlund theorem. Eur. J. Comb.34 (2013) 391–409. Zbl06111989MR2994406
10. [10] T. Harju and M. Linna, On the periodicity of morphisms on free monoids. RAIRO ITA20 (1986) 47–54. Zbl0608.68065MR849965
11. [11] J. Honkala, A decision method for the recognizability of sets defined by number systems. RAIRO ITA20 (1986) 395–403. Zbl0639.68074MR880843
12. [12] J. Honkala, Cancellation and periodicity properties of iterated morphisms. Theoret. Comput. Sci.391 (2008) 61–64. Zbl1133.68037MR2381352
13. [13] J. Honkala, On the simplification of infinite morphic words. Theoret. Comput. Sci.410 (2009) 997–1000. Zbl1162.68031MR2492043
14. [14] J. Honkala and M. Rigo, Decidability questions related to abstract numeration systems. Discrete Math.285 (2004) 329–333. Zbl1076.68040MR2062858
15. [15] R.A. Horn and C.R. Johnson, Matrix analysis. Cambridge University Press (1990). Zbl0704.15002MR1084815
16. [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. Zbl1216.68147MR2766741
17. [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. [18] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995). Zbl1106.37301MR1369092
19. [19] A. Maes and M. Rigo, More on generalized automatic sequences. J. Autom. Lang. Comb.7 (2002) 351–376. Zbl1033.68069MR1957696
20. [20] I. Mitrofanov, A proof for the decidability of HD0L ultimate periodicity. arXiv:1110.4780 (2011). 
21. [21] A. Muchnik, The definable criterion for definability in Presburger arithmetic and its applications. Theoret. Comput. Sci.290 (2003) 1433–1444. Zbl1052.68079MR1937730
22. [22] J.-J. Pansiot, Hiérarchie et fermeture de certaines classes de tag-systèmes. Acta Informatica20 (1983) 179–196. Zbl0507.68046MR727164
23. [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. Zbl0554.68053MR784265
24. [24] J.-J. Pansiot, Decidability of periodicity for infinite words. RAIRO ITA20 (1986) 43–46. Zbl0617.68063MR849964
25. [25] N. Priebe, Towards a characterization of self-similar tilings in terms of derived Voronoĭ tessellations. Geom. Dedicata79 (2000) 239–265. Zbl1048.37014MR1755727
26. [26] N. Priebe and B. Solomyak, Characterization of planar pseudo-self-similar tilings. Discrete Comput. Geom.26 (2001) 289–306. Zbl0997.52012MR1854103
27. [27] M. Queffélec, Substitution dynamical systems–spectral analysis. In Lect. Notes Math., Vol. 1294. Springer-Verlag (1987). Zbl0642.28013MR924156
28. [28] O. Salon, Suites automatiques à multi-indices. In Séminaire de Théorie des Nombres de Bordeaux (1986-1987) 4.01–4.27. Zbl0653.10049
29. [29] O. Salon, Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris305 (1987) 501–504. Zbl0628.10007MR916320