{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:08:54Z","timestamp":1772370534641,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2021,12]]},"DOI":"10.1007\/s00493-020-4311-x","type":"journal-article","created":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T22:02:51Z","timestamp":1637359371000},"page":"765-801","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Substitutive Systems and a Finitary Version of Cobham\u2019s Theorem"],"prefix":"10.1007","volume":"41","author":[{"given":"Jakub","family":"Byszewski","sequence":"first","affiliation":[]},{"given":"Jakub","family":"Konieczny","sequence":"additional","affiliation":[]},{"given":"El\u017cbieta","family":"Krawczyk","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,20]]},"reference":[{"key":"4311_CR1","doi-asserted-by":"publisher","first-page":"2337","DOI":"10.1016\/j.jalgebra.2007.06.039","volume":"319","author":"B Adamozewski","year":"2008","unstructured":"B. Adamozewski and J. P. Bell: Function fields in positive characteristic: expansions and Cobham\u2019s theorem, J. Algebra 319 (2008), 2337\u20132350.","journal-title":"J. Algebra"},{"key":"4311_CR2","doi-asserted-by":"publisher","first-page":"4421","DOI":"10.1090\/S0002-9947-2011-05357-2","volume":"363","author":"B Adamczewski","year":"2011","unstructured":"B. Adamczewski and J. P. Bell: An analogue of Cobham\u2019s theorem for fractals, Trans. Amer. Math. Soc. 363 (2011), 4421\u20134442.","journal-title":"Trans. Amer. Math. Soc."},{"key":"4311_CR3","first-page":"1301","volume":"17","author":"B Adamczewski","year":"2017","unstructured":"B. Adamczewski and J. P. Bell: A problem about Mahler functions, Ann. Sc. Norm. Super. Pisa Cl. Sci. 17 (2017), 1301\u20131355.","journal-title":"Ann. Sc. Norm. Super. Pisa Cl. Sci."},{"key":"4311_CR4","doi-asserted-by":"publisher","first-page":"2795","DOI":"10.1016\/j.tcs.2009.02.006","volume":"410","author":"J-P Allouche","year":"2009","unstructured":"J.-P. Allouche, N. Rampersad and J. Shallit: Periodicity, repetitions, and orbits of an automatic sequence, Theoret. Comput. Sci. 410 (2009), 2795\u20132803.","journal-title":"Theoret. Comput. Sci."},{"key":"4311_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546563","volume-title":"Automatic sequences","author":"J-P Allouche","year":"2003","unstructured":"J.-P. Allouche and J. Shallit: Automatic sequences, Cambridge University Press, Cambridge, 2003, Theory, applications, generalizations."},{"key":"4311_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S1446788713000074","volume":"93","author":"J-P Allouche","year":"2012","unstructured":"J.-P. Allouche and J. Shallit: A variant of Hofstadter\u2019s sequence and finite automata, J. Aust. Math. Soc. 93 (2012), 1\u20138.","journal-title":"J. Aust. Math. Soc."},{"key":"4311_CR7","unstructured":"J. P. Bell: A generalization of Cobham\u2019s theorem for regular sequences, S\u00e9m. Lothar. Combin. 54A (2005\/07), Art. B54Ap. 15."},{"key":"4311_CR8","doi-asserted-by":"publisher","first-page":"2896","DOI":"10.1017\/etds.2017.144","volume":"39","author":"V Berth\u00e9","year":"2019","unstructured":"V. Berth\u00e9, W. Steiner, J. M. Thuswaldner and R. Yassawi: Recognizability for sequences of morphisms, Ergodic Theory and Dynamical Systems 39 (2019), 2896\u20132931.","journal-title":"Ergodic Theory and Dynamical Systems"},{"key":"4311_CR9","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1017\/S0143385708000230","volume":"29","author":"S Bezuglyi","year":"2009","unstructured":"S. Bezuglyi, J. Kwiatkowski and K. Medynets: Aperiodic substitution systems and their Bratteli diagrams, Ergodic Theory Dynam. Systems 29 (2009), 37\u201372.","journal-title":"Ergodic Theory Dynam. Systems"},{"key":"4311_CR10","doi-asserted-by":"publisher","first-page":"1694","DOI":"10.1016\/j.tcs.2008.12.051","volume":"410","author":"B Boigelot","year":"2009","unstructured":"B. Boigelot and J. Brusten: A generalization of Cobham\u2019s theorem to automata over real numbers, Theoret. Comput. Sci. 410 (2009), 1694\u20131703.","journal-title":"Theoret. Comput. Sci."},{"key":"4311_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2168\/LMCS-6(1:6)2010","volume":"6","author":"B Boigelot","year":"2010","unstructured":"B. Boigelot, J. Brusten and V. Bruy\u00e8re: On the sets of real numbers recognized by finite automata in multiple bases, Log. Methods Comput. Sci. 6 (2010), 1\u201317.","journal-title":"Log. Methods Comput. Sci."},{"key":"4311_CR12","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/978-3-642-02959-2_34","volume-title":"A generalization of Semenov\u2019s theorem to automata over real numbers","author":"B Boigelot","year":"2009","unstructured":"B. Boigelot, J. Brusten and J. Leroux: A generalization of Semenov\u2019s theorem to automata over real numbers, Automated deduction - CADE-22, Lecture Notes in Comput. Sci., vol. 5663, Springer, Berlin, 2009, 469\u2013484."},{"key":"4311_CR13","first-page":"191","volume":"1","author":"V Bruy\u00e8re","year":"1994","unstructured":"V. Bruy\u00e8re, G. Hansel, Ch. Michaux and R. Villemaire: Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. Simon Stevin 1 (1994), 191\u2013238, Journ\u00e9es Montoises (Mons, 1992).","journal-title":"Bull. Belg. Math. Soc. Simon Stevin"},{"key":"4311_CR14","doi-asserted-by":"publisher","first-page":"235","DOI":"10.4064\/aa180626-13-1","volume":"192","author":"J Byszewski","year":"2020","unstructured":"J. Byszewski and J. Konieczny: A density version of Cobham\u2019s theorem, Acta Arith. 192 (2020), 235\u2013247.","journal-title":"Acta Arith."},{"key":"4311_CR15","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.aim.2015.04.008","volume":"280","author":"E Charlier","year":"2015","unstructured":"E. Charlier, J. Leroy and M. Rigo: An analogue of Cobham\u2019s theorem for graph directed iterated function systems, Adv. Math. 280 (2015), 86\u2013120.","journal-title":"Adv. Math."},{"key":"4311_CR16","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(79)90011-2","volume":"9","author":"G Christol","year":"1979","unstructured":"G. Christol: Ensembles presque p\u00e9riodiques k-reconnaissables, Theoret. Comput. Sci. 9 (1979), 141\u2013145.","journal-title":"Theoret. Comput. Sci."},{"key":"4311_CR17","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/BF01746527","volume":"3","author":"A Cobham","year":"1969","unstructured":"A. Cobham: On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 (1969), 186\u2013192.","journal-title":"Math. Systems Theory"},{"key":"4311_CR18","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/BF01706087","volume":"6","author":"A Cobham","year":"1972","unstructured":"A. Cobham: Uniform tag sequences, Math. Systems Theory 6 (1972), 164\u2013192.","journal-title":"Math. Systems Theory"},{"key":"4311_CR19","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.disc.2014.01.002","volume":"322","author":"J D Currie","year":"2014","unstructured":"J. D. Currie, N. Rampersad, K. Saari and L. Q. Zamboni: Extremal words in morphic subshifts, Discrete Math. 322 (2014), 53\u201360.","journal-title":"Discrete Math."},{"key":"4311_CR20","doi-asserted-by":"crossref","first-page":"1799","DOI":"10.4171\/jems\/294","volume":"13","author":"F Durand","year":"2011","unstructured":"F. Durand: Cobham\u2019s theorem for substitutions, J. Eur. Math. Soc. (JEMS) 13 (2011), 1799\u20131814.","journal-title":"J. Eur. Math. Soc. (JEMS)"},{"key":"4311_CR21","unstructured":"F. Durand and M. Rigo: On Cobham\u2019s theorem, (2011), https:\/\/hal.archives-ouvertes.fr\/hal-00605375."},{"key":"4311_CR22","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-85729-021-2","volume-title":"Ergodic theory with a view towards number theory","author":"M Einsiedler","year":"2011","unstructured":"M. Einsiedler and T. Ward: Ergodic theory with a view towards number theory, Graduate Texts in Mathematics, vol. 259, Springer-Verlag London, Ltd., London, 2011."},{"key":"4311_CR23","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1017\/S0143385709000121","volume":"30","author":"M Elekes","year":"2010","unstructured":"M. Elekes, T. Keleti and A. M\u00e1th\u00e9: Self-similar and self-affine sets: measure of the intersection of two copies, Ergodic Theory Dynam. Systems 30 (2010), 399\u2013440.","journal-title":"Ergodic Theory Dynam. Systems"},{"key":"4311_CR24","doi-asserted-by":"publisher","first-page":"401","DOI":"10.2140\/pjm.1958.8.401","volume":"8","author":"R Ellis","year":"1958","unstructured":"R. Ellis: Distal transformation groups, Pacific J. Math. 8 (1958), 401\u2013405.","journal-title":"Pacific J. Math."},{"key":"4311_CR25","series-title":"Cambridge Studies in Advanced Mathematics","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316160749","volume-title":"Unit equations in Diophantine number theory","author":"J-H Evertse","year":"2015","unstructured":"J.-H. Evertse and K. Gy\u0151ry: Unit equations in Diophantine number theory, Cambridge Studies in Advanced Mathematics, vol. 146, Cambridge University Press, Cambridge, 2015."},{"key":"4311_CR26","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0304-3975(96)00239-3","volume":"172","author":"I Fagnot","year":"1997","unstructured":"I. Fagnot: Sur les facteurs des mots automatiques, Theoret. Comput. Sci. 172 (1997), 67\u201389.","journal-title":"Theoret. Comput. Sci."},{"key":"4311_CR27","doi-asserted-by":"publisher","first-page":"1964","DOI":"10.1016\/j.aim.2009.06.022","volume":"222","author":"D-J Feng","year":"2009","unstructured":"D.-J. Feng and Y. Wang: On the structures of generating iterated function systems of Cantor sets, Adv. Math. 222 (2009), 1964\u20131981.","journal-title":"Adv. Math."},{"key":"4311_CR28","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1051\/ita\/1986200403951","volume":"20","author":"J Honkala","year":"1986","unstructured":"J. Honkala: A decision method for the recognizability of sets defined by number systems, RAIRO Inform. Th\u00e9or. Appl. 20 (1986), 395\u2013403.","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"4311_CR29","doi-asserted-by":"publisher","first-page":"379","DOI":"10.5802\/jtnb.551","volume":"18","author":"K S Kedlaya","year":"2006","unstructured":"K. S. Kedlaya: Finite automata and algebraic extensions of function fields, J. Theor. Nombres Bordeaux 18 (2006), 379\u2013420.","journal-title":"J. Theor. Nombres Bordeaux"},{"key":"4311_CR30","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/j.jda.2015.03.006","volume":"33","author":"K Klouda","year":"2015","unstructured":"K. Klouda: and S. Starosta: An algorithm for enumerating all infinite repetitions in a D0L-system, J. Discrete Algorithms 33 (2015), 130\u2013138.","journal-title":"J. Discrete Algorithms"},{"key":"4311_CR31","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/BF02698777","volume":"6","author":"S Lang","year":"1960","unstructured":"S. Lang: Integral points on curves, Publ. Math. Inst. Hautes Etudes Sci. 6 (1960), 27\u201343.","journal-title":"Publ. Math. Inst. Hautes Etudes Sci."},{"key":"4311_CR32","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566097","volume-title":"Combinatorics on words","author":"M Lothaire","year":"1997","unstructured":"M. Lothaire: Combinatorics on words, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1997."},{"key":"4311_CR33","series-title":"Encyclopedia of Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019","volume-title":"Algebraic combinatorics on words","author":"M Lothaire","year":"2002","unstructured":"M. Lothaire: Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002."},{"key":"4311_CR34","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/BF01448915","volume":"107","author":"K Mahler","year":"1933","unstructured":"K. Mahler: Zur Approximation algebraischer Zahlen. I, Math. Ann. 107 (1933), 691\u2013730.","journal-title":"Math. Ann."},{"key":"4311_CR35","doi-asserted-by":"publisher","first-page":"1086","DOI":"10.1017\/etds.2016.58","volume":"38","author":"G R Maloney","year":"2018","unstructured":"G. R. Maloney and D. Rust: Beyond primitivity for one-dimensional substitution subshifts and tiling spaces, Ergodic Theory Dynam. Systems 38 (2018), 1086\u20131117.","journal-title":"Ergodic Theory Dynam. Systems"},{"key":"4311_CR36","doi-asserted-by":"publisher","first-page":"1363","DOI":"10.1142\/S0129054119500308","volume":"30","author":"L Mol","year":"2019","unstructured":"L. Mol, N. Rampersad, J. Shallit and M. Stipulanti: Cobham\u2019s theorem and automaticity, Internat. J. Found. Comput. Sci. 30 (2019), 1363\u20131379.","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"4311_CR37","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11212-6","volume-title":"Substitution dynamical systems - spectral analysis","author":"M Queff\u00e9lec","year":"2010","unstructured":"M. Queff\u00e9lec: Substitution dynamical systems - spectral analysis, second ed., Lecture Notes in Mathematics, vol. 1294, Springer-Verlag, Berlin, 2010.","edition":"second ed."},{"key":"4311_CR38","series-title":"Pure and Applied Mathematics","volume-title":"The mathematical theory of L systems","author":"G Rozenberg","year":"1980","unstructured":"G. Rozenberg and A. Salomaa: The mathematical theory of L systems, Pure and Applied Mathematics, vol. 90, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980."},{"key":"4311_CR39","unstructured":"R. Sch\u00e4fke and M. F. Singer: Mahler equations and rationality, (2017), Preprint. arXiv:1605.08830 [math.CA]."},{"key":"4311_CR40","first-page":"403","volume":"18","author":"A L Semenov","year":"1977","unstructured":"A. L. Semenov: The Presburger nature of predicates that are regular in two number systems, Sibirsk. Mat. \u017d. 18 (1977), 403\u2013418.","journal-title":"Sibirsk. Mat. \u017d."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-020-4311-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-020-4311-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-020-4311-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T18:24:19Z","timestamp":1726165459000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-020-4311-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,20]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["4311"],"URL":"https:\/\/doi.org\/10.1007\/s00493-020-4311-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,20]]},"assertion":[{"value":"3 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}