{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T03:43:29Z","timestamp":1778643809215,"version":"3.51.4"},"reference-count":32,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"vor","delay-in-days":181,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["2018-04118"],"award-info":[{"award-number":["2018-04118"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["2016-03632"],"award-info":[{"award-number":["2016-03632"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2022,2,15]]},"published-print":{"date-parts":[[2022]]},"abstract":"<jats:p>Given a right-infinite word x over a finite alphabet<jats:italic>A<\/jats:italic>, the<jats:italic>rank<\/jats:italic>of x is the size of the smallest set<jats:italic>S<\/jats:italic>of words over<jats:italic>A<\/jats:italic>such that x can be realized as an infinite concatenation of words in<jats:italic>S<\/jats:italic>. We show that the property of having rank two is decidable for the class of<jats:italic>k<\/jats:italic>-automatic words for each integer<jats:italic>k<\/jats:italic>\u2265 2.<\/jats:p>","DOI":"10.1051\/ita\/2022006","type":"journal-article","created":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T07:59:03Z","timestamp":1656662343000},"page":"7","source":"Crossref","is-referenced-by-count":1,"title":["Automatic sequences of rank two"],"prefix":"10.1051","volume":"56","author":[{"given":"Jason P.","family":"Bell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1197-3820","authenticated-orcid":false,"given":"Jeffrey","family":"Shallit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2022,7,1]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Allouche J.-P. and Shallit J., Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003).","DOI":"10.1017\/CBO9780511546563"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Barwise J., An introduction to first-order logic. In Handbook of Mathematical Logic, edited by Barwise J.. North-Holland (1977), pp. 5\u201346.","DOI":"10.1016\/S0049-237X(08)71097-8"},{"key":"R3","doi-asserted-by":"crossref","first-page":"809","DOI":"10.1142\/S0218196709005330","volume":"19","author":"Bell","year":"2009","journal-title":"Internat. J. Algebra Comput"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Bell J.P. and Shallit J., Lie complexity of words. Available at 31 (2021).","DOI":"10.1016\/j.tcs.2022.06.001"},{"key":"R5","first-page":"191","volume":"1","author":"Bruyere","year":"1994","journal-title":"Bull. Belgian Math. Soc"},{"key":"R6","unstructured":"Charlier E., Massuir A., Rigo M. and Rowland E., Ultimate periodicity problem for linear numeration systems. Preprint at 31 (2020)."},{"key":"R7","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1142\/S0129054112400448","volume":"23","author":"Charlier","year":"2012","journal-title":"Internat. J. Found. Comp. Sci"},{"key":"R8","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/978-3-642-59136-5_6","volume":"1","author":"Choffrut","year":"1997","journal-title":"Handbook of Formal Languages"},{"key":"R9","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/BF01706087","volume":"6","author":"Cobham","year":"1972","journal-title":"Math. Systems Theory"},{"key":"R10","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0012-365X(96)00118-5","volume":"160","author":"Culik","year":"1996","journal-title":"Discrete Math"},{"key":"R11","first-page":"201","volume":"47","author":"Durand","year":"2013","journal-title":"RAIRO: ITA"},{"key":"R12","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0304-3975(89)90080-7","volume":"21","author":"Ehrenfeucht","year":"1982","journal-title":"Theoret. Comput. Sci"},{"key":"R13","first-page":"13","volume":"53","author":"Ehrenfeucht","year":"1983","journal-title":"Inform. Comput"},{"key":"R14","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1007\/978-3-642-38771-5_23","volume":"7907","author":"Goc","year":"2013","journal-title":"Lecture Notes in Computer Science"},{"key":"R15","first-page":"47","volume":"20","author":"Harju","year":"1986","journal-title":"RAIRO: ITA"},{"key":"R16","first-page":"395","volume":"20","author":"Honkala","year":"1986","journal-title":"RAIRO: ITA"},{"key":"R17","unstructured":"Hopcroft J.E. and Ullman J.D., Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979)."},{"key":"R18","unstructured":"Jeandel E. and Rao M., An aperiodic set of 11 Wang tiles. Preprint https:\/\/arxiv.org\/abs\/1506.06492 (2015)."},{"key":"R19","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0012-365X(95)00120-L","volume":"160","author":"Kari","year":"1996","journal-title":"Discrete Math"},{"key":"R20","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/j.jda.2015.03.006","volume":"33","author":"Klouda","year":"2015","journal-title":"J. Discrete Algor"},{"key":"R21","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/j.tcs.2019.04.021","volume":"790","author":"Klouda","year":"2019","journal-title":"Theoret. Comput. Sci"},{"key":"R22","unstructured":"Klouda K. and Starosta S., Repetitiveness of HD0L-systems. Unpublished manuscript (2021)."},{"key":"R23","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0304-3975(99)00238-8","volume":"240","author":"Kobayashi","year":"2000","journal-title":"Theoret. Comput. Sci"},{"key":"R24","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0304-3975(91)90169-3","volume":"82","author":"Lando","year":"1991","journal-title":"Theoret. Comput. Sci"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Leroux J., 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\u2013156.","DOI":"10.1109\/LICS.2005.2"},{"key":"R26","first-page":"64","volume":"186","author":"Linna","year":"1984","journal-title":"Ann. Univ. Turku. Ser. A I"},{"key":"R27","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1307\/mmj\/1028998766","volume":"9","author":"Lyndon","year":"1962","journal-title":"Michigan Math. J"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Marsault V. and Sakarovitch J., Ultimate periodicity of b-recognisable sets: a quasilinear procedure. In B\u00e9al M.P. and Carton O., editors, Developments in Language Theory, 17th International Conference, DLT 2013, Vol. 7907 of Lecture Notes in Computer Science. Springer-Verlag (2013) 362\u2013373.","DOI":"10.1007\/978-3-642-38771-5_32"},{"key":"R29","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.tcs.2004.09.016","volume":"330","author":"Matiyasevich","year":"2005","journal-title":"Theoret. Comput. Sci"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"Mignosi F. and S\u00e9\u00e9bold P., If a D0L language is k-power free then it is circular. In Lingas A., Karlsson R. and Carlsson S., editors, Proc. 20th Int'l Conf. on Automata, Languages, and Programming (ICALP), Vol. 700 of Lecture Notes in Computer Science (1993) 507\u2013518.","DOI":"10.1007\/3-540-56939-1_98"},{"key":"R31","first-page":"43","volume":"20","author":"Pansiot","year":"1986","journal-title":"RAIRO: ITA"},{"key":"R32","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","volume":"52","author":"Post","year":"1946","journal-title":"Bull. Amer. Math. Soc"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2022006\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,28]],"date-time":"2024-09-28T07:33:21Z","timestamp":1727508801000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2022006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"references-count":32,"alternative-id":["ita210036"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2022006","relation":{},"ISSN":["0988-3754","2804-7346"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"2804-7346","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]}}}