Automatic Sequences of Rank Two
RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 7

Given a right-infinite word x over a finite alphabet A, the rank of x is the size of the smallest set S of words over A such that x can be realized as an infinite concatenation of words in S. We show that the property of having rank two is decidable for the class of k-automatic words for each integer k ≥ 2.

DOI : 10.1051/ita/2022006
Classification : 68R15, 11B85
Keywords: Combinatorics on words, automatic sequence, primitive word, rank two 
@article{ITA_2022__56_1_A7_0,
     author = {Bell, Jason P. and Shallit, Jeffrey},
     title = {Automatic {Sequences} of {Rank} {Two}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     doi = {10.1051/ita/2022006},
     mrnumber = {4446537},
     zbl = {07609840},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2022006/}
}
TY  - JOUR
AU  - Bell, Jason P.
AU  - Shallit, Jeffrey
TI  - Automatic Sequences of Rank Two
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2022
VL  - 56
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2022006/
DO  - 10.1051/ita/2022006
LA  - en
ID  - ITA_2022__56_1_A7_0
ER  - 
%0 Journal Article
%A Bell, Jason P.
%A Shallit, Jeffrey
%T Automatic Sequences of Rank Two
%J RAIRO. Theoretical Informatics and Applications
%D 2022
%V 56
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2022006/
%R 10.1051/ita/2022006
%G en
%F ITA_2022__56_1_A7_0
Bell, Jason P.; Shallit, Jeffrey. Automatic Sequences of Rank Two. RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 7. doi: 10.1051/ita/2022006

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

[2] J. Barwise, An introduction to first-order logic. In Handbook of Mathematical Logic, edited by J. Barwise. North-Holland (1977), pp. 5–46. | MR

[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. | MR | Zbl | DOI

[4] J. P. Bell and J. Shallit, Lie complexity of words. Available at (2021). | arXiv | MR | Zbl

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

[6] E. Charlier, A. Massuir, M. Rigo and E. Rowland, Ultimate periodicity problem for linear numeration systems. Preprint at (2020). | arXiv | MR | Zbl

[7] E. Charlier, N. Rampersad and J. Shallit, Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comp. Sci. 23 (2012) 1035–1066. | MR | Zbl | DOI

[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. | MR | DOI

[9] A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972) 164–192. | MR | Zbl | DOI

[10] K. Culik Ii, An aperiodic set of 13 Wang tiles. Discrete Math. 160 (1996) 245–251. | MR | Zbl | DOI

[11] F. Durand, Decidability of the HD0L ultimate periodicity problem. RAIRO: ITA 47 (2013) 201–214. | MR | Zbl | Numdam

[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. | MR | Zbl | DOI

[13] A. Ehrenfeucht and G. Rozenberg, Repetition of subwords in D0L languages. Inform. Comput. 53 (1983) 13–35. | MR | Zbl

[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. | MR | Zbl | DOI

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

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

[17] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). | MR | Zbl

[18] E. Jeandel and M. Rao, An aperiodic set of 11 Wang tiles. Preprint (2015). | arXiv | MR | Zbl

[19] J. Kari, A small aperiodic set of Wang tiles. Discrete Math. 160 (1996) 259–264. | MR | Zbl | DOI

[20] K. Klouda and S. Starosta, An algorithm for enumerating all infinite repetitions in a DOL-system. J. Discrete Algor. 33 (2015) 130–138. | MR | Zbl | DOI

[21] K. Klouda and S. Starosta, Characterization of circular D0L-systems. Theoret. Comput. Sci. 790 (2019) 131–137. | MR | Zbl | DOI

[22] K. Klouda and S. Starosta, Repetitiveness of HD0L-systems. Unpublished manuscript (2021).

[23] Y. Kobayashi and F. Otto, Repetitiveness of languages generated by morphisms. Theoret. Comput. Sci. 240 (2000) 337–378. | MR | Zbl | DOI

[24] B. Lando, Periodicity and ultimate periodicity of D0L systems. Theoret. Comput. Sci. 82 (1991) 19–33. | MR | Zbl | DOI

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

[26] M. Linna, On periodic ω -sequences obtained by iterating morphisms. Ann. Univ. Turku. Ser. A I 186 (1984) 64–71. | MR | Zbl

[27] R. C. Lyndon and M. P. Schutzenberger, The equation aM = bNcP in a free group. Michigan Math. J. 9 (1962) 289–298. | MR | Zbl | DOI

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

[29] Y. Matiyasevich and G. Sénizergues, Decision problems for semi-Thue systems with a few rules. Theoret. Comput. Sci. 330 (2005) 145–169. | MR | Zbl | DOI

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

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

[32] E. L. Post, A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc. 52 (1946) 264–268. | MR | Zbl | DOI

Cité par Sources :

Jason Bell is supported by NSERC grant 2016-03632. Jeffrey Shallit is supported by NSERC grant 2018-04118.