{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:40Z","timestamp":1760202640814},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385353"},{"type":"electronic","value":"9783642385360"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_5","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T01:03:04Z","timestamp":1370221384000},"page":"49-63","source":"Crossref","is-referenced-by-count":8,"title":["Decidability and Enumeration for Automatic Sequences: A Survey"],"prefix":"10.1007","author":[{"given":"Jeffrey","family":"Shallit","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0304-3975(01)00212-2","volume":"292","author":"J.P. Allouche","year":"2003","unstructured":"Allouche, J.P., Baake, M., Cassaigne, J., Damanik, D.: Palindrome complexity. Theoret. Comput. Sci.\u00a0292, 9\u201331 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR2","unstructured":"Allouche, J.P., Currie, J., Shallit, J.: Extremal infinite overlap-free binary words. European J. Combinatorics 5, R27 (1998), http:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v5i1r27"},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"2795","DOI":"10.1016\/j.tcs.2009.02.006","volume":"410","author":"J.P. Allouche","year":"2009","unstructured":"Allouche, J.P., Rampersad, N., Shallit, J.: Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci.\u00a0410, 2795\u20132803 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Allouche, J.P., Shallit, J.: The ubiquitous Prouhet-Thue-Morse sequence. In: Ding, C., Helleseth, T., Niederreiter, H. (eds.) Proceedings of Sequences and Their Applications, SETA 1998, pp. 1\u201316. Springer (1999)","DOI":"10.1007\/978-1-4471-0551-0_1"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Allouche, J.P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003)","DOI":"10.1017\/CBO9780511546563"},{"key":"5_CR6","unstructured":"Berstel, J.: Axel Thue\u2019s work on repetitions in words. In: Leroux, P., Reutenauer, C. (eds.) S\u00e9ries Formelles et Combinatoire Alg\u00e9brique, Publications du LaCim, Universit\u00e9 du Qu\u00e9bec \u00e0 Montr\u00e9al, vol.\u00a011, pp. 65\u201380 (1992)"},{"issue":"2-3","key":"5_CR7","first-page":"39","volume":"19","author":"A. Blondin Mass\u00e9","year":"2008","unstructured":"Blondin Mass\u00e9, A., Brlek, S., Garon, A., Labb\u00e9, S.: Combinatorial properties of f-palindromes in the Thue-Morse sequence. Pure Math. Appl.\u00a019(2-3), 39\u201352 (2008), http:\/\/www.mat.unisi.it\/newsito\/puma\/public_html\/19_2_3\/4.pdf","journal-title":"Pure Math. Appl."},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0166-218X(92)90274-E","volume":"24","author":"S. Brlek","year":"1989","unstructured":"Brlek, S.: Enumeration of factors in the Thue-Morse word. Disc. Appl. Math.\u00a024, 83\u201396 (1989)","journal-title":"Disc. Appl. Math."},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1051\/ita:2006030","volume":"40","author":"S. Brown","year":"2006","unstructured":"Brown, S., Rampersad, N., Shallit, J., Vasiga, T.: Squares and overlaps in the Thue-Morse sequence and some variants. RAIRO Inform. Th\u00e9or. App.\u00a040, 473\u2013484 (2006)","journal-title":"RAIRO Inform. Th\u00e9or. App."},{"key":"5_CR10","doi-asserted-by":"crossref","first-page":"191","DOI":"10.36045\/bbms\/1103408547","volume":"1","author":"V. Bruy\u00e8re","year":"1994","unstructured":"Bruy\u00e8re, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and p-recognizable sets of integers. Bull. Belgian Math. Soc.\u00a01, 191\u2013238 (1994); Corrigendum, Bull. Belg. Math. Soc. 1, 577 (1994)","journal-title":"Bull. Belgian Math. Soc."},{"key":"#cr-split#-5_CR11.1","doi-asserted-by":"crossref","unstructured":"B\u00fcchi, J.R.: Weak secord-order arithmetic and finite automata. Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik\u00a06, 66-92 (1960)","DOI":"10.1002\/malq.19600060105"},{"key":"#cr-split#-5_CR11.2","doi-asserted-by":"crossref","unstructured":"reprinted in Mac Lane, S., Siefkes, D. (eds.): The Collected Works of J. Richard B\u00fcchi, pp. 398-424. Springer (1990)","DOI":"10.1007\/978-1-4613-8928-6"},{"key":"5_CR12","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.), pp. 1\u201311. Stanford University Press (1962)"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1142\/S0218196709004968","volume":"19","author":"A. Carpi","year":"2009","unstructured":"Carpi, A., D\u2019Alonzo, V.: On the repetitivity index of infinite words. Internat. J. Algebra Comput.\u00a019, 145\u2013158 (2009)","journal-title":"Internat. J. Algebra Comput."},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"3932","DOI":"10.1016\/j.tcs.2010.08.005","volume":"411","author":"A. Carpi","year":"2010","unstructured":"Carpi, A., D\u2019Alonzo, V.: On factors of synchronized sequences. Theoret. Comput. Sci.\u00a0411, 3932\u20133937 (2010)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1051\/ita:2001129","volume":"35","author":"A. Carpi","year":"2001","unstructured":"Carpi, A., Maggi, C.: On synchronized sequences and their separators. RAIRO Inform. Th\u00e9or. App.\u00a035, 513\u2013524 (2001)","journal-title":"RAIRO Inform. Th\u00e9or. App."},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1142\/S0129054112400448","volume":"23","author":"E. Charlier","year":"2012","unstructured":"Charlier, E., Rampersad, N., Shallit, J.: Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comp. Sci.\u00a023, 1035\u20131066 (2012)","journal-title":"Internat. J. Found. Comp. Sci."},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/BF01706087","volume":"6","author":"A. Cobham","year":"1972","unstructured":"Cobham, A.: Uniform tag sequences. Math. Systems Theory\u00a06, 164\u2013192 (1972)","journal-title":"Math. Systems Theory"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"4742","DOI":"10.1016\/j.tcs.2011.04.036","volume":"41","author":"J. Currie","year":"2011","unstructured":"Currie, J.: Lexicographically least words in the orbit closure of the Rudin-Shapiro word. Theoret. Comput. Sci.\u00a041, 4742\u20134746 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1051\/ita:2008006","volume":"43","author":"J.D. Currie","year":"2009","unstructured":"Currie, J.D., Saari, K.: Least periods of factors of infinite words. RAIRO Inform. Th\u00e9or. App.\u00a043, 165\u2013178 (2009)","journal-title":"RAIRO Inform. Th\u00e9or. App."},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Dekking, F.M., Mend\u00e8s France, M., van der Poorten, A.J.: Folds! Math. Intelligencer 4, 130\u2013138, 173\u2013181, 190\u2013195 (1982); erratum 5, 5 (1983)","DOI":"10.1007\/BF03023552"},{"key":"5_CR21","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","volume":"98","author":"C.C. Elgot","year":"1961","unstructured":"Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc.\u00a098, 21\u201351 (1961)","journal-title":"Trans. Amer. Math. Soc."},{"key":"5_CR22","first-page":"633","volume":"32","author":"M. Euwe","year":"1929","unstructured":"Euwe, M.: Mengentheoretische Betrachtungen \u00fcber das Schachspiel. Proc. Konin. Akad. Wetenschappen, Amsterdam\u00a032, 633\u2013642 (1929)","journal-title":"Proc. Konin. Akad. Wetenschappen, Amsterdam"},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-31606-7_16","volume-title":"Implementation and Application of Automata","author":"D. Go\u010d","year":"2012","unstructured":"Go\u010d, D., Henshall, D., Shallit, J.: Automatic theorem-proving in combinatorics on words. In: Moreira, N., Reis, R. (eds.) CIAA 2012. LNCS, vol.\u00a07381, pp. 180\u2013191. Springer, Heidelberg (2012)"},{"key":"5_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-37064-9_27","volume-title":"Language and Automata Theory and Applications","author":"D. Go\u010d","year":"2013","unstructured":"Go\u010d, D., Mousavi, H., Shallit, J.: On the number of unbordered factors. In: Dediu, A.-H., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2013. LNCS, vol.\u00a07810, pp. 299\u2013310. Springer, Heidelberg (2013)"},{"key":"5_CR25","unstructured":"Go\u010d, D., Schaeffer, L., Shallit, J.: The subword complexity of k-automatic sequences is k-synchronized (2012) (submitted), preprint available at http:\/\/arxiv.org\/abs\/1206.5352"},{"key":"5_CR26","unstructured":"Go\u010d, D., Schaeffer, L., Shallit, J.: A new approach to the paperfolding sequences (manuscript in preparation, 2013)"},{"key":"5_CR27","first-page":"39","volume":"7","author":"B. Hodgson","year":"1983","unstructured":"Hodgson, B.: D\u00e9cidabilit\u00e9 par automate fini. Ann. Sci. Math. Qu\u00e9bec\u00a07, 39\u201357 (1983)","journal-title":"Ann. Sci. Math. Qu\u00e9bec"},{"key":"5_CR28","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1051\/ita\/1986200403951","volume":"20","author":"J. Honkala","year":"1986","unstructured":"Honkala, J.: A decision method for the recognizability of sets defined by number systems. RAIRO Inform. Th\u00e9or. App.\u00a020, 395\u2013403 (1986)","journal-title":"RAIRO Inform. Th\u00e9or. App."},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"Klaedtke, F.: Bounds on the automata size for Presburger arithmetic. ACM Trans. Comput. Logic\u00a09(2), article 11 (March 2008), http:\/\/doi.acm.org\/10.1145\/1342991.1342995","DOI":"10.1145\/1342991.1342995"},{"key":"5_CR30","doi-asserted-by":"publisher","first-page":"277","DOI":"10.2307\/3610126","volume":"41","author":"J. Leech","year":"1957","unstructured":"Leech, J.: A problem on strings of beads. Math. Gazette\u00a041, 277\u2013278 (1957)","journal-title":"Math. Gazette"},{"key":"5_CR31","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), pp. 147\u2013156. IEEE Press (2005)"},{"key":"5_CR32","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0304-3975(89)90013-3","volume":"63","author":"A.D. Luca","year":"1989","unstructured":"Luca, A.D., Varricchio, S.: Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups. Theoret. Comput. Sci.\u00a063, 333\u2013348 (1989)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR33","unstructured":"Marsault, V., Sakarovitch, J.: Ultimate periodicity of b-recognisable sets: a quasilinear procedure (2013), preprint available at http:\/\/arxiv.org\/abs\/1301.2691"},{"key":"5_CR34","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1090\/S0002-9947-1921-1501161-8","volume":"22","author":"M. Morse","year":"1921","unstructured":"Morse, M.: Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc.\u00a022, 84\u2013100 (1921)","journal-title":"Trans. Amer. Math. Soc."},{"key":"5_CR35","doi-asserted-by":"publisher","first-page":"815","DOI":"10.2307\/2371264","volume":"60","author":"M. Morse","year":"1938","unstructured":"Morse, M., Hedlund, G.A.: Symbolic dynamics. Amer. J. Math.\u00a060, 815\u2013866 (1938)","journal-title":"Amer. J. Math."},{"key":"5_CR36","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/0020-0190(81)90004-1","volume":"12","author":"J.J. Pansiot","year":"1981","unstructured":"Pansiot, J.J.: The Morse sequence and iterated morphisms. Inform. Process. Lett.\u00a012, 68\u201370 (1981)","journal-title":"Inform. Process. Lett."},{"key":"5_CR37","unstructured":"Presburger, M.: \u00dcber die Volst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In: Sparawozdanie z I Kongresu Matematyk\u00f3w Kraj\u00f3w Slowianskich, Warsaw, pp. 92\u2013101 (1929)"},{"key":"5_CR38","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1080\/014453409108837187","volume":"12","author":"M. Presburger","year":"1991","unstructured":"Presburger, M.: On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation. Hist. Phil. Logic\u00a012, 225\u2013233 (1991)","journal-title":"Hist. Phil. Logic"},{"key":"5_CR39","first-page":"225","volume":"33","author":"E. Prouhet","year":"1851","unstructured":"Prouhet, E.: M\u00e9moire sur quelques relations entre les puissances des nombres. C. R. Acad. Sci. Paris\u00a033, 225 (1851)","journal-title":"C. R. Acad. Sci. Paris"},{"key":"5_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-642-28332-1_42","volume-title":"Language and Automata Theory and Applications","author":"E. Rowland","year":"2012","unstructured":"Rowland, E., Shallit, J.: k-automatic sets of rational numbers. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol.\u00a07183, pp. 490\u2013501. Springer, Heidelberg (2012)"},{"key":"5_CR41","unstructured":"Schaeffer, L.: Abelian powers in automatic sequences are not always automatic. Talk at CanadaDAM 2013 Conference, St. John\u2019s, Newfoundland (June 2013)"},{"key":"5_CR42","doi-asserted-by":"crossref","unstructured":"Schaeffer, L., Shallit, J.: The critical exponent is computable for automatic sequences. Int. J. Found. Comput. Sci. (2012) (to appear)","DOI":"10.1142\/S0129054112400655"},{"key":"5_CR43","doi-asserted-by":"crossref","unstructured":"Shallit, J.: The critical exponent is computable for automatic sequences. In: Ambroz, P., Holub, S., M\u00e1sakov\u00e1, Z. (eds.) Proceedings 8th International Conference Words 2011. Elect. Proc. Theor. Comput. Sci, vol.\u00a063, pp. 231\u2013239 (2011)","DOI":"10.4204\/EPTCS.63.29"},{"key":"5_CR44","unstructured":"Sipser, M.: Introduction to the Theory of Computation. Cengage Learning, 3rd edn. (2013)"},{"key":"#cr-split#-5_CR45.1","unstructured":"Thue, A.: \u00dcber unendliche Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl.\u00a07, 1-22 (1906)"},{"key":"#cr-split#-5_CR45.2","unstructured":"reprinted in Nagell, T. (ed.): Selected Mathematical Papers of Axel Thue, Universitetsforlaget, Oslo, pp. 139-158 (1977)"},{"key":"#cr-split#-5_CR46.1","unstructured":"Thue, A.: \u00dcber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl\u00a01, 1-67 (1912)"},{"key":"#cr-split#-5_CR46.2","unstructured":"reprinted in Nagell, T. (ed.): Selected Mathematical Papers of Axel Thue, Universitetsforlaget, Oslo, pp. 413-478 (1977)"},{"key":"5_CR47","volume-title":"Algebra: Themes, Tools, Concepts","author":"A. Wah","year":"1994","unstructured":"Wah, A., Picciotto, H.: Algebra: Themes, Tools, Concepts. Creative Publications, Mountain View (1994), http:\/\/www.mathedpage.org\/attc\/attc.html"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,27]],"date-time":"2020-07-27T15:09:34Z","timestamp":1595862574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}