Open Access
RAIRO-Theor. Inf. Appl.
Volume 56, 2022
Article Number 7
Number of page(s) 13
Published online 01 July 2022
  1. J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). [Google Scholar]
  2. J. Barwise, An introduction to first-order logic. In Handbook of Mathematical Logic, edited by J. Barwise. North-Holland (1977), pp. 5–46. [CrossRef] [Google Scholar]
  3. J. Bell, E. Charlier, A. Fraenkel and M. Rigo, A decision problem for ultimately periodic sets in non-standard numeration systems. Internat. J. Algebra Comput. 19 (2009) 809–839. [CrossRef] [MathSciNet] [Google Scholar]
  4. J.P. Bell and J. Shallit, Lie complexity of words. Available at 31 (2021). [Google Scholar]
  5. V. Bruyere, G. Hansel, C. Michaux and R. Villemaire, Logic and p-recognizable sets of integers. Bull. Belgian Math. Soc. 1 (1994) 191–238. Corrigendum, Bull. Belg. Math. Soc. 1 (1994) 577. [Google Scholar]
  6. E. Charlier, A. Massuir, M. Rigo and E. Rowland, Ultimate periodicity problem for linear numeration systems. Preprint at 31 (2020). [Google Scholar]
  7. E. Charlier, N. Rampersad and J. Shallit, Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comp. Sci. 23 (2012) 1035–1066. [CrossRef] [Google Scholar]
  8. C. Choffrut and J. Karhumaki. Combinatorics of words. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, Vol. 1, pp. 329–438. Springer-Verlag, 1997. [CrossRef] [Google Scholar]
  9. A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972) 164–192. [Google Scholar]
  10. K. Culik II, An aperiodic set of 13 Wang tiles. Discrete Math. 160 (1996) 245–251. [CrossRef] [MathSciNet] [Google Scholar]
  11. F. Durand, Decidability of the HD0L ultimate periodicity problem. RAIRO: ITA 47 (2013) 201–214. [Google Scholar]
  12. A. Ehrenfeucht, J. Karhumaaki and G. Rozenberg, The (generalized) Post correspondence problem with lists consisting of two words is decidable. Theoret. Comput. Sci. 21 (1982) 119–144. [CrossRef] [MathSciNet] [Google Scholar]
  13. A. Ehrenfeucht and G. Rozenberg, Repetition of subwords in D0L languages. Inform. Comput. 53 (1983) 13–35. [Google Scholar]
  14. D. Goc, L. Schaeffer and J. Shallit, The subword complexity of fc-automatic sequences is fc-synchronized. In DLT 2013, Vol. 7907 of Lecture Notes in Computer Science, edited by M.-P. Beal and O. Carton. Springer-Verlag (2013) 252–263. [CrossRef] [Google Scholar]
  15. T. Harju and M. Linna, On the periodicity of morphisms on free monoids. RAIRO: ITA 20 (1986) 47–54. [Google Scholar]
  16. J. Honkala, A decision method for the recognizability of sets defined by number systems. RAIRO: ITA 20 (1986) 395–403. [Google Scholar]
  17. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). [Google Scholar]
  18. E. Jeandel and M. Rao, An aperiodic set of 11 Wang tiles. Preprint (2015). [Google Scholar]
  19. J. Kari, A small aperiodic set of Wang tiles. Discrete Math. 160 (1996) 259–264. [CrossRef] [MathSciNet] [Google Scholar]
  20. K. Klouda and S. Starosta, An algorithm for enumerating all infinite repetitions in a DOL-system. J. Discrete Algor. 33 (2015) 130–138. [CrossRef] [Google Scholar]
  21. K. Klouda and S. Starosta, Characterization of circular D0L-systems. Theoret. Comput. Sci. 790 (2019) 131–137. [CrossRef] [MathSciNet] [Google Scholar]
  22. K. Klouda and S. Starosta, Repetitiveness of HD0L-systems. Unpublished manuscript (2021). [Google Scholar]
  23. Y. Kobayashi and F. Otto, Repetitiveness of languages generated by morphisms. Theoret. Comput. Sci. 240 (2000) 337–378. [CrossRef] [MathSciNet] [Google Scholar]
  24. B. Lando, Periodicity and ultimate periodicity of D0L systems. Theoret. Comput. Sci. 82 (1991) 19–33. [CrossRef] [MathSciNet] [Google Scholar]
  25. 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 Press (2005) 147–156. [Google Scholar]
  26. M. Linna, On periodic !-sequences obtained by iterating morphisms. Ann. Univ. Turku. Ser. A I 186 (1984) 64–71. [Google Scholar]
  27. R.C. Lyndon and M.P. Schutzenberger, The equation aM = bNcP in a free group. Michigan Math. J. 9 (1962) 289–298. [CrossRef] [MathSciNet] [Google Scholar]
  28. V. Marsault and J. Sakarovitch, Ultimate periodicity of b-recognisable sets: a quasilinear procedure. In M.P. Béal and O. Carton, editors, Developments in Language Theory, 17th International Conference, DLT 2013, Vol. 7907 of Lecture Notes in Computer Science. Springer-Verlag (2013) 362–373. [Google Scholar]
  29. Y. Matiyasevich and G. Sénizergues, Decision problems for semi-Thue systems with a few rules. Theoret. Comput. Sci. 330 (2005) 145–169. [CrossRef] [MathSciNet] [Google Scholar]
  30. F. Mignosi and P. Séébold, If a D0L language is k-power free then it is circular. In A. Lingas, R. Karlsson and S. Carlsson, editors, Proc. 20th Int'l Conf. on Automata, Languages, and Programming (ICALP), Vol. 700 of Lecture Notes in Computer Science (1993) 507–518. [Google Scholar]
  31. J.-J. Pansiot, Decidability of periodicity for infinite words. RAIRO: ITA 20 (1986) 43–46. [Google Scholar]
  32. E.L. Post, A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc. 52 (1946) 264–268. [CrossRef] [MathSciNet] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.