Bibliography

Jeffrey Shallit

doi:10.1017/9781108775267.016

Albert, M. H. and Linton, S.. A practical algorithm for reducing non-deterministic finite state automata. Technical Report OUCS-2004-11, University of Otago, 2004.Google Scholar

Allouche, G., Allouche, J.-P., and Shallit, J.. Kolams indiens, dessins sur le sable aux iles Vanuatu, courbe de Sierpinski, et morphismes de mono'ide. Ann. Inst. Fourier (Grenoble) 56 (2006), 2115–2130.Google Scholar

Allouche, J.-P.. Automates finis en theorie des nombres. Exposition. Math. 5 (1987), 239–266.Google Scholar

Allouche, J.-P.. The number of factors in a paperfolding sequence. Bull. Austral. Math. Soc. 46 (1992), 23–32.Google Scholar

Allouche, J.-P., Astoorian, D., Randall, J., and Shallit, J.. Morphisms, squarefree strings, and the Tower of Hanoi puzzle. Amer. Math. Monthly 101 (1994), 651658.Google Scholar

Allouche, J.-P., Baake, M., Cassaigne, J., and Damanik, D.. Palindrome complexity. Theoret. Comput. Sci. 292 (2003), 9–31.Google Scholar

Allouche, J.-P., Betrema, J., and Shallit, J.. Sur des points fixes de morphismes du mono'ide libre. RAIRO Inform. Theor. App. 23 (1989), 235–249.Google Scholar

Allouche, J.-P. and Bousquet-Melou, M.. Canonical positions for the factors in the paperfolding sequences. Theoret. Comput. Sci. 129 (1994), 263–278.Google Scholar

Allouche, J.-P. and Bousquet-Melou, M.. Facteurs des suites de Rudin-Shapiro generalisees. Bull. Belgian Math. Soc. 1 (1994), 145–164.Google Scholar

Allouche, J.-P., Currie, J., and Shallit, J.. Extremal infinite overlap-free binary words. Electron. J. Combin. 5 (1998), R27.CrossRef Google Scholar

Allouche, J.-P., Rampersad, N., and Shallit, J.. On integer sequences whose first iterates are linear. Aequationes Math. 69 (2005), 114–127.Google Scholar

Allouche, J.-P., Rampersad, N., and Shallit, J.. Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410 (2009), 2795–2803.CrossRef Google Scholar

Allouche, J.-P. and Sapir, A.. Restricted Towers of Hanoi and morphisms. In De Felice, C. and Restivo, A., editors, DLT 2005, Vol. 3572 of Lecture Notes in Computer Science, pp. 1–10. Springer-Verlag, 2005.Google Scholar

Allouche, J.-P. and Shallit, J. O.. The ring of fc-regular sequences. Theoret. Comput. Sci. 98 (1992), 163–197.Google Scholar

Allouche, J.-P. and Shallit, J.. The ubiquitous Prouhet-Thue-Morse sequence. In Ding, C., Helleseth, T., and Niederreiter, H., editors, Sequences and Their Applications, Proceedings of SETA '98, pp. 1–16. Springer-Verlag, 1999.Google Scholar

Allouche, J.-P. and Shallit, J.. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003.Google Scholar

Allouche, J.-P. and Shallit, J. O.. The ring of k-regular sequences, II. Theoret. Comput. Sci. 307 (2003), 3–29.Google Scholar

Allouche, J.-P., Shallit, J., and Yassawi, R.. How to prove that a sequence is not automatic. Arxiv preprint arXiv:2104.13072 [math.NT], available at arxiv.org/abs/2104.13072, 2021.Google Scholar

Apostolico, A. and Brimkov, V. E.. Fibonacci arrays and their two-dimensional repetitions. Theoret. Comput. Sci. 237 (2000), 263–273.Google Scholar

Ardila, F.. The coefficients of a Fibonacci power series. Fibonacci Quart. 42 (2004), 202–204.Google Scholar

Arnoux, P. and Rauzy, G.. Representation geometrique de suites de complexite 2n + 1. Bull. Soc. Math. France 119 (1991), 199–215.Google Scholar

Au, Y. H., Drexler-Lemire, C., and Shallit, J.. Notes and note pairs in N0rgard's infinity series. J. Math. Music 11 (2017), 1–19.Google Scholar

Avgustinovich, S., Karhumaki, J., and Puzynina, S.. On abelian versions of critical factorization theorem. RAIRO Inform. Theor. App. 46 (2012), 3–15.Google Scholar

Badkobeh, G., Fici, G., and Liptak, Z.. On the number of closed factors in a word. In Dediu, A.-H., Formenti, E., Martin-Vide, C., and Truthe, B., editors, Language and Automata Theory and Applications, LATA 2015, Vol. 8977 of Lecture Notes in Computer Science, pp. 381–390. Springer-Verlag, 2015.Google Scholar

Badkobeh, G. and Ochem, P.. Avoiding conjugacy classes on the 5-letter alphabet. RAIRO Inform. Theor. App. 54 (2020), Paper 2.Google Scholar

Balister, P. and Gerke, S.. The asymptotic number of prefix normal words. Theoret. Comput. Sci. 784 (2019), 75–80.Google Scholar

Baranwal, A. R.. Decision algorithms for Ostrowski-automatic sequences. Master's thesis, University of Waterloo, School of Computer Science, 2020.Google Scholar

Baranwal, A. R., Schaeffer, L., and Shallit, J.. Ostrowski-automatic sequences: theory and applications. Theoret. Comput. Sci. 858 (2021), 122–142.Google Scholar

Baranwal, A. R. and Shallit, J.. Critical exponent of infinite balanced words via the Pell number system. In Merca§, R. and Reidenbach, D., editors, WORDS 2019, Vol. 11682 of Lecture Notes in Computer Science, pp. 80–92. Springer-Verlag, 2019.Google Scholar

Bateman, P. T., Jockusch, C. G., and Woods, A. R.. Decidability and undecidability of theories with a predicate for the primes. J. Symbolic Logic 58 (1993), 672687.CrossRef Google Scholar

Baum, L. E. and Sweet, M. M.. Continued fractions of algebraic power series in characteristic 2. Ann. Math. 103 (1976), 593–610.Google Scholar

Beatty, S.. Problem 3173. Amer. Math. Monthly 33 (1926), 159. Solution, 34 (1927), 159–160.Google Scholar

Bell, J., Charlier, E., Fraenkel, A., and Rigo, M.. A decision problem for ultimately periodic sets in non-standard numeration systems. Internat. J. Algebra Comput. 19 (2009), 809–839.Google Scholar

Bell, J. P., Coons, M., and Hare, K. G.. The minimal growth of a fc-regular sequence. Bull. Austral. Math. Soc. 90 (2014), 195–203.Google Scholar

Bell, J., Hare, K., and Shallit, J.. When is an automatic set an additive basis? Proc. Amer. Math. Soc. Ser. B 5 (2018), 50–63.Google Scholar

Bell, J., Lidbetter, T. F., and Shallit, J.. Additive number theory via approximation by regular languages. In Hoshi, M. and Seki, S., editors, DLT2018, Vol. 11088 of Lecture Notes in Computer Science, pp. 121–132. Springer-Verlag, 2018.Google Scholar

Bell, J., Lidbetter, T. F., and Shallit, J.. Additive number theory via approximation by regular languages. Internat. J. Found. Comp. Sci. 31 (2020), 667–687.Google Scholar

Bell, J. P. and Madill, B. W.. Iterative algebras. Algebr. Represent. Theory 18 (2015), 1533–1546.Google Scholar

Bell, J. P. and Shallit, J.. Lie complexity of words. Arxiv preprint arXiv:2102.03821 [cs.FL], available at arxiv.org/abs/2102.0 3821, 2021.Google Scholar

Bellissard, J., Bovier, A., and Ghez, J.-M.. Spectral properties of a tight binding Hamiltonian with period doubling potential. Commun. Math. Phys. 135 (1991), 379–399.Google Scholar

Berlekamp, E. R., Conway, J. H., and Guy, R. K.. Winning Ways for Your Mathematical Plays, Vol. 1. Academic Press, 1982.Google Scholar

Berstel, J.. Sur les mots sans carre definis par un morphisme. In Maurer, H. A., editor, Proc. 6th Int'l Conf. on Automata, Languages, and Programming (ICALP), Vol. 71 of Lecture Notes in Computer Science, pp. 16–25. Springer-Verlag, 1979.Google Scholar

Berstel, J.. Mots de Fibonacci. Seminaire d'Informatique Theorique, LITP 6–7 (1980-81), 57–78.Google Scholar

Berstel, J.. Fibonacci words—a survey. In Rozenberg, G. and Salomaa, A., editors, The Book ofL, pp. 13–27. Springer-Verlag, 1986.Google Scholar

Berstel, J.. Axel Thue's work on repetitions in words. In Leroux, P. and Reutenauer, C., editors, Series Formelles et Combinatoire Algebrique, Vol. 11 of Publications du LaCim, pp. 65-80. Universite du Quebec a Montreal, 1992.Google Scholar

Berstel, J., Lauve, A., Reutenauer, C., and Saliola, F. V.. Combinatorics on Words: Christoffel Words and Repetitions in Words, Vol. 27 of CRM Monograph Series. Amer. Math. Soc., 2009.Google Scholar

Berstel, J. and Reutenauer, C.. Noncommutative Rational Series With Applications, Vol. 137 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 2011.Google Scholar

Bes, A.. A survey of arithmetical definability. Bull. Belgian Math. Soc. (2001), 1-54. Supplementary volume, M. Crabbe, F. Point, and C. Michaux, eds., A Tribute to Maurice Boffa.Google Scholar

Blondel, V. D., Theys, J., and Vladimirov, A. A.. An elementary counterexample to the finiteness conjecture. SIAMJ. Matrix Anal. Appl. 24 (2003), 963–970.Google Scholar

Blondin Masse, A., Brlek, S., Garon, A., and Labbe, S.. Combinatorial properties of f -palindromes in the Thue-Morse sequence. Pure Math. Appl. 19(2-3) (2008), 39–52.Google Scholar

Blondin Masse, A., de Carufel, J., Goupil, A., Lapointe, M., Nadeau, E., and Van-domme, E.. Leaf realization problem, caterpillar graphs and prefix normal words. Theoret. Comput. Sci. 732 (2018), 1–13.Google Scholar

Borchert, A. and Rampersad, N.. Words with many palindrome pair factors. Electron. J. Combin. 22 (2015), #P4.23 (electronic). Available at tinyurl.com/2p8 7wsrz.Google Scholar

Brlek, S.. Enumeration of factors in the Thue-Morse word. Disc. Appl. Math. 24 (1989), 83–96.Google Scholar

Brown, S., Rampersad, N., Shallit, J., and Vasiga, T.. Squares and overlaps in the Thue-Morse sequence and some variants. RAIRO Inform. Theor. App. 40 (2006), 473–484.Google Scholar

Bruyere, V. and Hansel, G.. Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181 (1997), 17–43.Google Scholar

Bruyere, V., Hansel, G., Michaux, C., and Villemaire, R.. Logic and p-recognizable sets of integers. Bull. Belgian Math. Soc. 1 (1994), 191–238.Google Scholar Google Scholar

Bucci, M., de Luca, A., and De Luca, A.. Rich and periodic-like words. In Diekert, V. and Nowotka, D., editors, Developments in Language Theory, DLT 2009, Vol. 5583 of Lecture Notes in Computer Science, pp. 145–155. Springer-Verlag, 2009.Google Scholar

Bucci, M., De Luca, A., and Fici, G.. Enumeration and structure of trapezoidal words. Theoret. Comput. Sci. 468 (2013), 12–22.Google Scholar

Bucci, M., De Luca, A., Glen, A., and Zamboni, L. Q.. A new characteristic property of rich words. Theoret. Comput. Sci. 410 (2009), 2860–2863.Google Scholar

Bucci, M., De Luca, A., and Zamboni, L. Q.. Reversible Christoffel factorizations. Theoret. Comput. Sci. 495 (2013), 17–24.Google Scholar

Buchi, J. R.. Weak secord-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6 (1960), 66-92. Reprinted in S. Mac Lane and D. Siefkes, eds., The Collected Works of J. Richard Buchi, Springer-Verlag, 1990, pp. 398424.Google Scholar

Buchi, J. R.. On a decision method in restricted second order arithmetic. In Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.), pp. 1–11. Stanford University Press, 1962.Google Scholar

Bugeaud, Y. and Kim, D. H.. A new complexity function, repetitions in Sturmian words, and irrationality exponents of Sturmian numbers. Trans. Amer. Math. Soc. 371 (2019), 3281–3308.Google Scholar

Bugeaud, Y., Krieger, D., and Shallit, J.. Morphic and automatic words: maximal blocks and diophantine approximation. ActaArith. 149 (2011), 181–199.Google Scholar

Burcsi, P., Fici, G., Liptak, Z., Ruskey, F., and Sawada, J.. On prefix normal words and prefix normal forms. Theoret. Comput. Sci. 659 (2017), 1–13.Google Scholar

Carlitz, L.. Fibonacci representations. Fibonacci Quart. 6 (1968), 193–220.Google Scholar

Carlitz, L., Scoville, R., and Hoggatt, V. E. Jr. Fibonacci representations. Fibonacci Quart. 10 (1972), 1-28. Addendum, 10 (1972), 527–530.Google Scholar

Carlitz, L., Scoville, R., and Hoggatt, V. E. Jr. Fibonacci representations of higher order. Fibonacci Quart. 10 (1972), 43-69,94.Google Scholar

Carpi, A. and D'Alonzo, V.. On the repetitivity index of infinite words. Internat. J. Algebra Comput. 19 (2009), 145–158.Google Scholar

Carpi, A. and Maggi, C.. On synchronized sequences and their separators. RAIRO Inform. Theor. App. 35 (2001), 513–524.Google Scholar

Cassaigne, J.. Special factors of sequences with linear subword complexity. In Dassow, J., Rozenberg, G., and Salomaa, A., editors, Developments in Language Theory II, pp. 25–34. World Scientific, 1996.Google Scholar

Cassaigne, J.. Sequences with grouped factors. In Developments in Language Theory III, pp. 211–222. Aristotle University of Thessaloniki, 1998.Google Scholar

Cerny, A.. Lyndon factorization of generalized words of Thue. Discrete Math. & Theoret. Comput. Sci. 5 (2002), 17–46.CrossRef Google Scholar

Charlier, E.. First-order logic and numeration systems. In Berthe, V. and Rigo, M., editors, Sequences, Groups, and Number Theory, pp. 89–141. Birkhauser, 2018.Google Scholar

Charlier, E., Massuir, A., Rigo, M., and Rowland, E.. Ultimate periodicity problem for linear numeration systems. Arxiv preprint arXiv:2007.08147 [cs.DM], available at arxiv.org/abs/2007.08147, 2020.Google Scholar

Charlier, E., Rampersad, N., Rigo, M., and Waxweiler, L.. The minimal automaton recognizing mN in a linear numeration system. INTEGERS—Elect. J. Comb. Numb. Theory 11B (2011), #A4 (electronic).Google Scholar

Charlier, E., Rampersad, N., and Shallit, J.. Enumeration and decidable properties of automatic sequences. In Mauri, G. and Leporati, A., editors, Developments in Language Theory, 15th International Conference, DLT 2011, Vol. 6795 of Lecture Notes in Computer Science, pp. 165–179. Springer-Verlag, 2011.Google Scholar

Charlier, E., Rampersad, N., and Shallit, J.. Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comp. Sci. 23 (2012), 1035–1066.Google Scholar

Chase, Z.. A new upper bound for separating words. Arxiv preprint arXiv:2007.12097 [math.CO], available at arxiv.org/abs/2007.12097, 2020.Google Scholar

Chase, Z.. Separating words and trace reconstruction. In STOC 2021, pp. 21-31. ACM, 2021.Google Scholar

Chekhova, N., Hubert, P., and Messaoudi, A.. Proprietes combinatoires, er- godiques et arithmetiques de la substitution de Tribonacci. J. Theorie Nombres Bordeaux 13 (2001), 371–394.Google Scholar

Chen, Y.-G. and Wang, B.. On additive properties of two special sequences. Acta Arith. 110 (2003), 299–303.Google Scholar

Chen, J. and Wen, Z.-X.. On the abelian complexity of generalized Thue-Morse sequences. Theoret. Comput. Sci. 780 (2019), 66–73.Google Scholar

Choffrut, C., Malcher, A., Mereghetti, C., and Palano, B.. First-order logics: some characterizations and closure properties. Acta Inform. 49 (2012), 225–248.Google Scholar

Chow, S. and Slattery, T.. On Fibonacci partitions. J. Number Theory 225 (2021), 310–326.Google Scholar

Christodoulakis, M. and Christou, M.. Abelian concepts in strings: a review. In Holub, J., Watson, B. W., and Zd'arek, J., editors, Festschriftfor BorivojMelichar, pp. 19–45. Czech Technical University, 2012.Google Scholar

Christou, M., Crochemore, M., and Iliopoulos, C. S.. Quasiperiodicities in Fibonacci strings. Ars Combin. 129 (2016), 211–225.Google Scholar

Chuan, W.-F.. Symmetric Fibonacci words. Fibonacci Quart. 31 (1993), 251255.Google Scholar

Church, A.. An unsolvable problem of elementary number theory. Amer. J. Math. 58 (1936), 345–363.Google Scholar

Cicalese, F., Liptak, Z., and Rossi, M.. On infinite prefix normal words. Theoret. Comput. Sci. 859 (2021), 134–148.Google Scholar

Cobham, A.. Uniform tag sequences. Math. Systems Theory 6 (1972), 164–192.Google Scholar

Condon, A.. The complexity of the max word problem and the power of one-way interactive proof systems. Comput. Complexity 3 (1993), 292–305.Google Scholar

Coons, M.. Regular sequences and the joint spectral radius. Internat. J. Found. Comp. Sci. 28 (2017), 135–140.Google Scholar

Coons, M. and Spiegelhofer, L.. Number theoretic aspects of regular sequences. In Berthe, V. and Rigo, M., editors, Sequences, Groups, and Number Theory, Trends in Mathematics, pp. 37–87. Springer-Verlag, 2018.Google Scholar

Coven, E. M. and Hedlund, G. A.. Sequences with minimal block growth. Math. Systems Theory 7 (1973), 138–153.Google Scholar

Crochemore, M.. An optimal algorithm for computing the repetitions in a word. Inform. Process. Lett. 12 (1981), 244–250.Google Scholar

Crochemore, M., Mignosi, F., and Restivo, A.. Automata and forbidden words. Inform. Process. Lett. 67 (1998), 111–117.Google Scholar

Cummings, L. J., Moore, D., and Karhumaki, J.. Borders of Fibonacci strings. J. Combin. Math. Combin. Comput. 20 (1996), 81–87.Google Scholar

Cummings, L. J. and Smyth, W. F.. Weak repetitions in strings. J. Combin. Math. Combin. Comput. 24 (1997), 33–48.Google Scholar

Cummings, R., Shallit, J., and Staadecker, P.. Mesosome avoidance. Arxiv preprint arXiv:2107.13813 [cs.DM], available at arxiv.org/abs/210 7.13813, 2021.Google Scholar

Currie, J.. Lexicographically least words in the orbit closure of the Rudin-Shapiro word. Theoret. Comput. Sci. 41 (2011), 4742–4746.Google Scholar

Currie, J., Harju, T., Ochem, P., and Rampersad, N.. Some further results on square- free arithmetic progressions in infinite words. Theoret. Comput. Sci. 799 (2019), 140–148.Google Scholar

Currie, J. D. and Johnson, J. T.. There are level ternary circular square-free words of length n for n + 5,7,9,10,14,17. Arxiv preprint arXiv:2005.06235 [math.CO], available at arxiv.org/abs/2005.0 6235, 2020.Google Scholar

Currie, J., Rampersad, N., and Shallit, J.. Binary words containing infinitely many overlaps. Electron. J. Combin. 13 (2006), #R82 (electronic).Google Scholar

Currie, J. D. and Saari, K.. Least periods of factors of infinite words. RAIRO Inform. Theor. App. 43 (2009), 165–178.Google Scholar

Currie, J. and Visentin, T.. On abelian 2-avoidable binary patterns. Acta Inform. 43 (2007), 521–533.Google Scholar

D'Alessandro, F.. A combinatorial problem on trapezoidal words. Theoret. Comput. Sci. 273 (2002), 11–33.Google Scholar

Damanik, D.. Local symmetries in the period-doubling sequence. Disc. Appl. Math. 100 (2000), 115–121.Google Scholar

Damanik, D. and Lenz, D.. Substitution dynamical systems: Characterization of linear repetitivity and applications. J. Math. Anal. Appl. 321 (2006), 766–780.Google Scholar

Davies, S.. State complexity of reversals of deterministic finite automata with output. In Campeanu, C., editor, CIAA 2018, Vol. 10977 of Lecture Notes in Computer Science, pp. 133–145. Springer-Verlag, 2018.Google Scholar

Davis, M.. A computer program for Presburger's algorithm. In Summaries of Talks Presented at the Summer Institute for Symbolic Logic, pp. 215-233. Institute for Defense Analysis, Princeton, NJ, 1957. Reprinted in J. Siemann and G. Wrightson, eds., Automation of Reasoning—Classical Papers on Computational Logic 1957-1966, Vol. 1, Springer, 1983, pp. 41–48.Google Scholar

Davis, C. and Knuth, D. E.. Number representations and dragon curves-I, II. J. Recreational Math.. 3 (1970), 66-81, 133–149.Google Scholar

Dean, R. A.. A sequence without repeats on x, x^-1, y, y^-1. Amer. Math. Monthly 72 (1965), 383–385.Google Scholar

de Bruijn, N. G.. On bases for the set of integers. Publ. Math. (Debrecen) 1 (1950), 232–242.Google Scholar

de Bruijn, N. G.. Some direct decompositions of the set of integers. Math. Comp. 18 (1964), 537–546.Google Scholar

Defant, C.. Anti-power prefixes of the Thue-Morse word. Electron. J. Combin. 24(1) (2017), #P1.32 (electronic). Available at tinyurl.com/mvv2zxpv.Google Scholar

Dejean, F.. Sur un theoreme de Thue. J. Combin. Theory. Ser. A 13 (1972), 90–99.Google Scholar

Dekking, F. M.. The Frobenius problem for homomorphic embeddings of languages into the integers. Theoret. Comput. Sci. 732 (2018), 73–79.Google Scholar

Dekking, F. M., Mendes France, M., and van der Poorten, A. J.. Folds! Math. Intelligencer 4 (1982), 130-138, 173-181, 190-195. Erratum, 5 (1983), 5.Google Scholar

Dekking, F. M., Shallit, J., and Sloane, N. J. A.. Queens in exile: non-attacking queens on infinite chess boards. Electron. J. Combin. 27 (2020), #P1.52 (electronic).Google Scholar

Demaine, E. D., Eisenstat, S., Shallit, J., and Wilson, D. A.. Remarks on separating words. In Holzer, M., Kutrib, M., and Pighizzini, G., editors, Descriptional Complexity of Formal Systems, 13th International Workshop, DCFS 2011, Vol. 6808 of Lecture Notes in Computer Science, pp. 147–157. Springer-Verlag, 2011.Google Scholar

Dombi, G.. Additive properties of certain sets. ActaArith. 103 (2002), 137–146.Google Scholar

Droubay, X.. Palindromes in the Fibonacci word. Inform. Process. Lett. 55 (1995), 217–221.Google Scholar

Droubay, X., Justin, J., and Pirillo, G.. Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001), 539–553.Google Scholar

Duchene, E. and Rigo, M.. A morphic approach to combinatorial games: the Tribonacci case. RAIRO Inform. Theor. App. 42 (2008), 375–393.Google Scholar

Du, C. F., Mousavi, H., Rowland, E., Schaeffer, L., and Shallit, J.. Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability. Theoret. Comput. Sci. 657 (2017), 146–162.Google Scholar

Du, C. F., Mousavi, H., Schaeffer, L., and Shallit, J.. Decision algorithms for Fibonacci-automatic words III: Enumeration and abelian properties. Internat. J. Found. Comp. Sci. 27 (2016), 943–963.CrossRef Google Scholar

Durand-Gasselin, A. and Habermehl, P.. On the use of non-deterministic automata for Presburger arithmetic. In Gastin, P. and Laroussinie, F., editors, CONCUR 2010, Vol. 6269 of Lecture Notes in Computer Science, pp. 373–387. Springer- Verlag, 2010.Google Scholar

Durand, F.. A characterization of substitutive sequences using return words. Discrete Math. 179 (1998), 89–101.CrossRef Google Scholar

Durand, F.. Decidability of uniform recurrence of morphic sequences. Internat. J. Found. Comp. Sci. 24 (2013), 123–146.Google Scholar

Durand, F.. Decidability of the HD0L ultimate periodicity problem. RAIRO Inform. Theor. App. 47 (2013), 201–214.Google Scholar

Duval, J. P.. Factorizing words over an ordered alphabet. J. Algorithms 4 (1983), 363–381.Google Scholar

Eilenberg, S.. Automata, Languages, and Machines, Vol. A. Academic Press, 1974.Google Scholar

Elgot, C. C.. Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc. 98 (1961), 21–51.Google Scholar

Endrullis, J., Grabmayer, C., Hendriks, D., and Zantema, H.. The degree of squares is an atom. In Manea, F. and Nowotka, D., editors, Proc. WORDS 2015, Vol. 9304 of Lecture Notes in Computer Science, pp. 109–121. Springer-Verlag, 2015.Google Scholar

Endrullis, J., Hendriks, D., and Klop, J. W.. Degrees of streams. INTEGERS— Elect. J. Comb. Numb. Theory 11B (2011), A6 (electronic).Google Scholar

Endrullis, J., Hendriks, D., and Klop, J. W.. Streams are forever. Bull. European Assoc. Theor. Comput. Sci., No. 109, (2013), 70–106.Google Scholar

Endrullis, J., Klop, J. W., Saarela, A., and Whiteland, M.. Degrees of transducibil- ity. In Manea, F. and Nowotka, D., editors, Proc. WORDS 2015, Vol. 9304 of Lecture Notes in Computer Science, pp. 1–13. Springer-Verlag, 2015.Google Scholar

Erdos, P.. Some unsolved problems. Magyar Tud. Akad. Mat. Kutato Int. Kozl. 6 (1961), 221–254.Google Scholar

Euwe, M.. Mengentheoretische Betrachtungen uber das Schachspiel. Proc. Konin. Akad. Wetenschappen, Amsterdam 32 (1929), 633–642.Google Scholar

Everest, G., van der Poorten, A., Shparlinski, I., and Ward, T.. Recurrence Sequences, Vol. 104 of Mathematical Surveys and Monographs. Amer. Math. Soc., 2003.Google Scholar

Fagnot, I.. Sur les facteurs des mots automatiques. Theoret. Comput. Sci. 172 (1997), 67–89.Google Scholar

Ferrante, J. and Rackoff, C. W.. A decision procedure for the first order theory of real addition with order. SIAM J. Comput. 4 (1975), 69–76.Google Scholar

Ferrante, J. and Rackoff, C. W.. The Computational Complexity of Logical Theories, Vol. 718 of Lecture Notes in Mathematics. Springer-Verlag, 1979.Google Scholar

Fici, G., Langiu, A., Lecroq, T., Lefebvre, A., Mignosi, F., Peltomaki, J., and Prieur-Gaston, E.. Abelian powers and repetitions in Sturmian words. Theoret. Comput. Sci. 635 (2016), 16–34.Google Scholar

Fici, G., Postic, M., and Silva, M.. Abelian antipowers in infinite words. Adv. in Appl. Math. 108 (2019), 67–78.Google Scholar

Fici, G., Restivo, A., Silva, M., and Zamboni, L. Q.. Anti-powers in infinite words. Arxiv preprint arXiv:1606.02868 [cs.DM], available at arxiv.org/abs/1606.02868, 2016.Google Scholar

Fici, G., Restivo, A., Silva, M., and Zamboni, L. Q.. Anti-powers in infinite words. J. Combin. Theory. Ser. A 157 (2018), 109–119.Google Scholar

Fici, G. and Shallit, J.. Properties of a class of Toeplitz words. Arxiv preprint arXiv:2112.12125 [cs.FL], available at arxiv.org/abs/2112.1212 5, 2021.Google Scholar

Fici, G. and Zamboni, L. Q.. On the least number of palindromes contained in an infinite word. Theoret. Comput. Sci. 481 (2013), 1–8.Google Scholar

Fischer, M. J. and Rabin, M. O.. Super-exponential complexity of Presburger arithmetic. In Karp, R. M., editor, Complexity of Computation, Vol. 7 of SIAM- AMS Proceedings, pp. 27-42. Amer. Math. Soc., 1974.Google Scholar

Fleischer, L. and Shallit, J.. Words avoiding reversed factors, revisited. Arxiv preprint arXiv:1911.11704 [cs.FL], available at arxiv.org/abs/1911.117 0 4, 2019.Google Scholar

Fleischer, L. and Shallit, J.. Automata, palindromes, and reversed subwords. J. Automata, Languages, and Combinatorics 26 (2021), 221–253.Google Scholar

Forsyth, M., Jayakumar, A., Peltomaki, J., and Shallit, J.. Remarks on privileged words. Internat. J. Found. Comp. Sci. 27 (2016), 431–442.CrossRef Google Scholar

Fraenkel, A. S.. Systems of numeration. Amer. Math. Monthly 92 (1985), 105114.Google Scholar

Fraenkel, A. S. and Simpson, J.. The exact number of squares in Fibonacci words. Theoret. Comput. Sci. 218 (1999), 95-106. Corrigendum, 547 (2014), 122.Google Scholar

Frougny, C.. Representations of numbers and finite automata. Math. Systems Theory 25 (1992), 37–60.Google Scholar

Frougny, C. and Solomyak, B.. On representation of integers in linear numeration systems. In Pollicott, M. and Schmidt, K., editors, Ergodic Theory of Z^d Actions (Warwick, 1993-1994), Vol. 228 of London Mathematical Society Lecture Note Series, pp. 345-368. Cambridge University Press, 1996.Google Scholar

Gabric, D., Shallit, J., and Zhong, X. F.. Avoidance of split overlaps. Discrete Math. 344 (2021), 112176.Google Scholar

Gamard, G., Ochem, P., Richomme, G., and Seebold, P.. Avoidability of circular formulas. Theoret. Comput. Sci. 726 (2018), 1–4.Google Scholar

Garel, E.. Separateurs dans les mots infinis engendres par morphismes. Theoret. Comput. Sci. 180 (1997), 81–113.Google Scholar

Gawrychowski, P., Krieger, D., Rampersad, N., and Shallit, J.. Finding the growth rate of a regular or context-free language in polynomial time. Internat. J. Found. Comp. Sci. 21 (2010), 597–618.Google Scholar

Geldenhuys, J., van der Merwe, B., and van Zijl, L.. Reducing nondeterministic finite automata with SAT solvers. In Yli-Jyra, A., Kornai, A., Sakarovitch, J., and Watson, B., editors, FSMNLP: International Workshop on Finite-State Methods and Natural Language Processing, 8th International Workshop, Vol. 6062 of Lecture Notes in Artificial Intelligence, pp. 81–92. Springer-Verlag, 2010.Google Scholar

Gilbert, E.. Gray codes and paths on the n-cube. Bell System Tech. J. 37 (1958), 815–826.Google Scholar

Glen, A.. Powers in a class of a-strict episturmian words. Theoret. Comput. Sci. 380 (2007), 330–354.Google Scholar

Glen, A., Justin, J., Widmer, S., and Zamboni, L. Q.. Palindromic richness. European J. Combin. 30 (2009), 510–531.Google Scholar

Glen, A., Leve, F., and Richomme, G.. Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci. 409 (2008), 578–600.Google Scholar

Goc, D., Henshall, D., and Shallit, J.. Automatic theorem-proving in combinatorics on words. In Moreira, N. and Reis, R., editors, Implementation and Application of Automata—17th International Conference, CIAA 2012, Vol. 7381 of Lecture Notes in Computer Science, pp. 180–191. Springer-Verlag, 2012.Google Scholar

Goc, D., Henshall, D., and Shallit, J.. Automatic theorem-proving in combinatorics on words. Internat. J. Found. Comp. Sci. 24 (2013), 781–798.Google Scholar

Goc, D., Mousavi, H., Schaeffer, L., and Shallit, J.. A new approach to the pa- perfolding sequences. In Beckmann, A. et al., editors, Computability in Europe, CIE 2015, Vol. 9136 of Lecture Notes in Computer Science, pp. 34–43. Springer- Verlag, 2015.Google Scholar

Goc, D., Mousavi, H., and Shallit, J.. On the number of unbordered factors. In Dediu, A. H., Martin-Vide, C., and Truthe, B., editors, Languages and Automata Theory and Applications—7th International Conference, LATA 2013, Vol. 7810 of Lecture Notes in Computer Science, pp. 299–310. Springer-Verlag, 2013.Google Scholar

Goc, D., Rampersad, N., Rigo, M., and Salimov, P.. On the number of abelian bordered words (with an example of automatic theorem-proving). Internat. J. Found. Comp. Sci. 25 (2014), 1097–1110.Google Scholar

Goc, D., Saari, K., and Shallit, J.. Primitive words and Lyndon words in automatic and linearly recurrent sequences. In Dediu, A. H., Martin-Vide, C., and Truthe, B., editors, Languages and Automata Theory and Applications—7th International Conference, LATA 2013, Vol. 7810 of Lecture Notes in Computer Science, pp. 311–322. Springer-Verlag, 2013.Google Scholar

Goc, D., Schaeffer, L., and Shallit, J.. Subword complexity and k-synchronization. In Beal, M.-P. and Carton, O., editors, DLT2013, Vol. 7907 of Lecture Notes in Computer Science, pp. 252–263. Springer-Verlag, 2013.Google Scholar

Goc, D. and Shallit, J.. Least periods of k-automatic sequences. Arxiv preprint arXiv:1207.5450 [cs.FL], available at arxiv.org/abs/1207.5450, 2012.Google Scholar

Golay, M. J. E.. Multi-slit spectrometry. J. Optical Soc. Amer. 39 (1949), 437444.Google Scholar

Golay, M. J. E.. Static multislit spectrometry and its application to the panoramic display of infrared spectra. J. Optical Soc. Amer. 41 (1951), 468–472.Google Scholar

Goralcik, P. and Koubek, V.. On discerning words by automata. In Kott, L., editor, Proc. 13th Int'l Conf. on Automata, Languages, and Programming (ICALP), Vol. 226 of Lecture Notes in Computer Science, pp. 116–122. Springer-Verlag, 1986.Google Scholar

Graham, R. L.. Covering the positive integers by disjoint sets of the form {[na + p] : n = 1,2,...}. J. Combin. Theory. Ser. A 15 (1973), 354–358.Google Scholar

Gries, D.. Describing an algorithm by Hopcroft. Acta Inform. 2 (1973), 97–109.Google Scholar

Guckenheimer, J.. On the bifurcation of maps of the interval. Inventiones Math. 39 (1977), 165–178.Google Scholar

Guepin, F., Haase, C., and Worrell, J.. On the existential theories of Buchi arithmetic and linear p-adic fields. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1–10. IEEE Computer Society, 2019.Google Scholar

Haase, C.. A survival guide to Presburger arithmetic. ACM SIGLOG News 5(3) (2018), 67–82.Google Scholar

Haase, C.. Approaching arithmetic theories with finite-state automata. In Lep-orati, A. et al., editors, LATA 2020, Vol. 12038 of Lecture Notes in Computer Science, pp. 33–43. Springer-Verlag, 2020.Google Scholar

Haase, C. and Rozycki, J.. On the expressiveness of Buchi arithmetic. In Kiefer, S. and Tasson, C., editors, Foundations ofSoftware Science and Computation Structures, FOSSACS 2021, Vol. 12650 of Lecture Notes in Computer Science, pp. 310–323. Springer-Verlag, 2021.Google Scholar

Hales, T. C.. Formal proof. Notices Amer. Math. Soc. 55(11) (2008), 1370–1380.Google Scholar

Haque, S. and Shallit, J.. Discriminators and k-regular sequences. INTEGERS— Elect. J. Comb. Numb. Theory 16 (2016), #A76 (electronic). Available at tinyurl.com/4 2 7 7ph9 6.Google Scholar

Hardy, G. H. and Wright, E. M.. An Introduction to the Theory of Numbers. Oxford University Press, 5th edition, 1985.Google Scholar

Harju, T.. Disposability in square-free words. Theoret. Comput. Sci. 862 (2021), 155–159.Google Scholar

Harju, T.. Avoiding square-free words on free groups. Arxiv preprint arXiv:2104.06837 [math.CO], available at arxiv.org/abs/2104.06837, 2021.Google Scholar

Harju, T. and Karki, T.. On the number of frames of binary words. Theoret. Comput. Sci. 412 (2011), 5276–5284.Google Scholar

Harju, T. and Linna, M.. On the periodicity of morphisms on free monoids. RAIRO Inform. Theor. App. 20 (1986), 47–54.Google Scholar

Heule, M. J. H. and Kullmann, O.. The science of brute force. Comm. ACM 60(8) (2017), 70–79.Google Scholar

Hieronymi, P., Ma, D., Oei Ma, R., Schaeffer, L., Schulz, C., and Shallit, J.. Decidability for Sturmian words. Arxiv preprint arXiv:2102.08207 [cs.LO], available at arxiv.org/abs/2102.082 07, 2021.Google Scholar

Hieronymi, P. and Terry, A. Jr. Ostrowski numeration systems, addition, and finite automata. Notre Dame J. Formal Logic 59 (2018), 215–232.Google Scholar

Hilbert, D.. Uber die stetige Abbildung einer Linie auf ein Flachenstuck. Math. Annalen 38 (1891), 459–460.Google Scholar

Hinz, A. M., Klavzar, S., Milutinovic, U., and Petr, C.. The Tower ofHanoi—Myths and Maths. Birkhauser, 2013.Google Scholar

Hodgson, B.. Decidabilite par automate fini. Ann. Sci. Math. Quebec 7 (1983), 39–57.Google Scholar

H0holdt, T., Jensen, H. E., and Justesen, J.. Aperiodic correlations and the merit factor of a class of binary sequences. IEEE Trans. Inform. Theory 31 (1985), 549–552.Google Scholar

Honkala, J.. A decision method for the recognizability of sets defined by number systems. RAIRO Inform. Theor. App. 20 (1986), 395–403.Google Scholar

Honkala, J.. Quasi-universal k-regular sequences. Theoret. Comput. Sci. 891 (2021), 84–89.Google Scholar

Hopcroft, J. E.. An n log n algorithm for minimizing the states in a finite automaton. In Kohavi, Z., editor, The Theory of Machines and Computation, pp. 189–196. Academic Press, New York, 1971.Google Scholar

Hopcroft, J. E. and Ullman, J. D.. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.Google Scholar

Huang, Y.-k. and Wen, Z.-y.. The number of fractional powers in the Fibonacci word. Arxiv preprint arXiv:1811.11444 [math.DS], available at arxiv.org/abs/1811.114 4 4, 2018.Google Scholar

Hubert, P.. Suites equilibrees. Theoret. Comput. Sci. 242 (2000), 91–108.Google Scholar

I, T., Inenaga, S., Bannai, H., and Takeda, M.. Counting and verifying maximal palindromes. In Chavez, E. and Lonardi, S., editors, String Processing and Information Retrieval - 17th International Symposium, SPIRE 2010, Vol. 6393 of Lecture Notes in Computer Science, pp. 135–146. Springer-Verlag, 2010.Google Scholar

Ido, A. and Melancon, G.. Lyndon factorization of the Thue-Morse word and its relatives. Discrete Math. & Theoret. Comput. Sci. 1 (1997), 43–52.Google Scholar

Ilie, L. and Yu, S.. Reducing NFAs by invariant equivalences. Theoret. Comput. Sci. 306 (2003), 373–390.Google Scholar

Ilie, L., Novarro, G., and Yu, S.. On NFA reductions. In Karhumaki, J., Maurer, H., Paun, G., and Rozenberg, G., editors, Theory is Forever, Vol. 3113 of Lecture Notes in Computer Science, pp. 112–124. Springer-Verlag, 2004.Google Scholar

Iliopoulos, C. S., Moore, D., and Smyth, W. F.. A characterization of the squares in a Fibonacci string. Theoret. Comput. Sci. 172 (1997), 281–291.Google Scholar

Jacob, G.. Decidabilite de la finitude des demi-groupes de matrices. In Theoretical Computer Science, Vol. 48 of Lecture Notes in Computer Science, pp. 259–269. Springer-Verlag, 1977.Google Scholar

Jacob, G.. Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices. Theoret. Comput. Sci. 5 (1977/78), 183–204.Google Scholar

Jacob, G.. La finitude des representations lineaires des semi-groupes est decidable. J. Algebra 52 (1978), 437–459.Google Scholar

Jacobs, K.. Invitation to Mathematics. Princeton University Press, 1992.Google Scholar

Jiang, T. and Ravikumar, B.. NFA minimization problems are hard. SIAM J. Comput. 22 (1993), 1117–1141.Google Scholar

Kabore, I. and Kientega, B.. Abelian complexity of Thue-Morse word over a ternary alphabet. In Brlek, S., Dolce, F., Reutenauer, C., and Vandomme, E., editors, WORDS 2017, Vol. 10432 of Lecture Notes in Computer Science, pp. 132143. Springer-Verlag, 2017.Google Scholar

Kao, J.-Y., Rampersad, N., Shallit, J., and Silva, M.. Words avoiding repetitions in arithmetic progressions. Theoret. Comput. Sci. 391 (2008), 126–137.Google Scholar

Kaplan, C. S. and Shallit, J.. A frameless 2-coloring of the plane lattice. Math. Mag. 94 (2021), 353–360.Google Scholar

Karhumaki, J.. On cube-free w-words generated by binary morphisms. Disc. Appl. Math. 5 (1983), 279–297.Google Scholar

Kawsumarng, S., Khemaratchatakumthorn, T., Noppakaew, P., and Pongsriiam, P.. Sumsets associated with Wythoff sequences and Fibonacci numbers. Period. Math. Hung. 82 (2021), 98–113.Google Scholar

Kellendonk, J., Lenz, D., and Savinien, J.. A characterization of subshifts with bounded powers. Discrete Math. 313 (2013), 2881–2894.Google Scholar

Kempa, D. and Prezza, N.. At the roots of dictionary compression: string attrac- tors. In STOC'18 Proceedings, pp. 827–840. ACM Press, 2018.Google Scholar

Klaedtke, F.. Bounds on the automata size for Presburger arithmetic. ACM Trans. Comput. Logic 9(2) (2008), Article 11.Google Scholar

Klavzar, S. and Shpectorov, S.. Asymptotic number of isometric generalized Fibonacci cubes. European J. Combin. 33 (2012), 220–226.Google Scholar

Knuth, D. E., Morris, J., and Pratt, V.. Fast pattern matching in strings. SIAM J. Comput. 6 (1977), 323–350.Google Scholar

Knuutila, T.. Re-describing an algorithm by Hopcroft. Theoret. Comput. Sci. 250 (2001), 333–363.Google Scholar

Kociumaka, T., Navarro, G., and Prezza, N.. Towards a definitive measure of repetitiveness. In Kohayakawa, Y. and Miyazawa, F. K., editors, LATIN 2020, Vol. 12118 of Lecture Notes in Computer Science, pp. 207–219. Springer-Verlag, 2020.Google Scholar

Konev, B. and Lisitsa, A.. A SAT attack on the Erdos discrepancy problem. Arxiv preprint arXiv:1402.2184 [cs.DM], available at arxiv.org/abs/14 02.218 4, 2014.Google Scholar

Krawchuk, C. and Rampersad, N.. Cyclic complexity of some infinite words and generalizations. INTEGERS—Elect. J. Comb. Numb. Theory 18A (2018), #A12 (electronic). Available at tinyurl.com/mr2k2cbw.Google Scholar

Krebs, T. J. P.. A more reasonable proof of Cobham's theorem. Internat. J. Found. Comp. Sci. 32 (2021), 203–207.Google Scholar

Krenn, D. and Shallit, J.. Decidability and k-regular sequences. Theoret. Comput. Sci. 907 (2022), 34–44.Google Scholar

Kutsukake, K., Matsumoto, T., Nakashima, Y., Inenaga, S., Bannai, H., and Takeda, M.. On repetitiveness measures of Thue-Morse words. In Boucher, C. and Thankachan, S. V., editors, SPIRE 2020, Vol. 12303 of Lecture Notes in Computer Science, pp. 213–220. Springer-Verlag, 2020.Google Scholar

Lambek, J. and Moser, L.. On some two way classifications of integers. Canad. Math. Bull. 2 (1959), 85–89.Google Scholar

Landman, B. M. and Robertson, A.. Ramsey Theory on the Integers, Vol. 73 of Student Mathematical Library. Amer. Math. Soc., 2015.Google Scholar

Lando, B.. Periodicity and ultimate periodicity of D0L systems. Theoret. Comput. Sci. 82 (1991), 19–33.Google Scholar

Leech, J.. A problem on strings of beads. Math. Gazette 41 (1957), 277–278.Google Scholar

Lehr, S.. Sums and rational multiples of q-automatic sequences are q-automatic. Theoret. Comput. Sci. 108 (1993), 385–391.Google Scholar

Lekkerkerker, C. G.. Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci. Simon Stevin 29 (1952), 190–195.Google Scholar

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–156. IEEE Press, 2005.Google Scholar

Lev, V. F.. Reconstructing integer sets from their representation functions. Electron. J. Combin. 11(1) (2004), #R78.Google Scholar

Leve, F. and Richomme, G.. Quasiperiodic infinite words: some answers. Bull. European Assoc. Theor. Comput. Sci., No. 84, (2004), 128–138.Google Scholar

Leve, F. and Richomme, G.. Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci. 372 (2007), 15–25.Google Scholar

Leve, F. and Richomme, G.. On quasiperiodic morphisms. In Karhumaki, J., Lepisto, A., and Zamboni, L., editors, Proc. WORDS 2013, Vol. 8079 of Lecture Notes in Computer Science, pp. 181–192. Springer-Verlag, 2013.Google Scholar

Linna, M.. On periodic ^-sequences obtained by iterating morphisms. Ann. Univ. Turku. Ser. A 1 186 (1984), 64–71.Google Scholar

Lothaire, M.. Combinatorics on Words, Vol. 17 of Encyclopedia ofMathematics and Its Applications. Addison-Wesley, 1983.Google Scholar

Lothaire, M.. Algebraic Combinatorics on Words, Vol. 90 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 2002.Google Scholar

de Luca, A.. On the combinatorics of finite words. Theoret. Comput. Sci. 218 (1999), 13–39.Google Scholar

de Luca, A., Glen, A., and Zamboni, L. Q.. Rich, Sturmian, and trapezoidal words. Theoret. Comput. Sci. 407 (2008), 569–573.Google Scholar

de Luca, A. and Mione, L.. On bispecial factors of the Thue-Morse word. Inform. Process. Lett. 49 (1994), 179–183.Google Scholar

de Luca, A. and Varricchio, S.. Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups. Theoret. Comput. Sci. 63 (1989), 333348.Google Scholar

Luchinin, S. and Puzynina, S.. Symmetry groups of infinite words. In Mor-eira, N. and Reis, R., editors, DLT 2021, Vol. 12811 of Lecture Notes in Computer Science, pp. 267–278. Springer-Verlag, 2021.Google Scholar

Lyndon, R. C. and Schutzenberger, M. P.. The equation a^M = b^Nc^P in a free group. Michigan Math. J. 9 (1962), 289–298.Google Scholar

Malitz, J.. Introduction to Mathematical Logic. Springer-Verlag, 1979.Google Scholar

Mandel, A. and Simon, I.. On finite semigroups of matrices. Theoret. Comput. Sci. 5 (1977/78), 101–111.Google Scholar

Mantaci, S., Restivo, A., Romana, G., Rosone, G., and Sciortino, M.. String attractors and combinatorics on words. In ICTCS 2019, Vol. 2504 of CEUR Workshop Proceedings, pp. 57-71, 2019. Available at ceur-ws.org/Vol-250 4/paper8.pdf.Google Scholar

Mantaci, S., Restivo, A., Romana, G., Rosone, G., and Sciortino, M.. A combinatorial view on string attractors. Theoret. Comput. Sci. 850 (2021), 236–248.Google Scholar

Marcus, S.. Symmetry phenomena in infinite words, with biological, philosophical and aesthetic relevance. Symmetry: Culture and Science 14/15 (2003-2004), 477–487.Google Scholar

Marsault, V. and Sakarovitch, J.. Ultimate periodicity of b-recognisable sets: A quasilinear procedure. In Beal, M. P. and Carton, O., editors, Developments in Language Theory, 17th International Conference, DLT 2013, Vol. 7907 of Lecture Notes in Computer Science, pp. 362–373. Springer-Verlag, 2013.Google Scholar

Matiyasevich, Y. V.. Hilbert's Tenth Problem. The MIT Press, 1993.Google Scholar

Melancon, G.. Lyndon factorization of infinite words. In Puech, C. and Reis-chuk, R., editors, STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Vol. 1046 of Lecture Notes in Computer Science, pp. 147154. Springer-Verlag, 1996.Google Scholar

Melancon, G.. Lyndon word. In Hazewinkel, M., editor, Encyclopedia of Mathematics. Springer-Verlag, 2001.Google Scholar

Merca§, R., Ochem, P., Samsonov, A. V., and Shur, A. M.. Binary patterns in binary cube-free words: avoidability and growth. RAIRO Inform. Theor. App. 48 (2014), 369–389.Google Scholar

Mignosi, F. and Pirillo, G.. Repetitions in the Fibonacci infinite word. RAIRO Inform. Theor. App. 26 (1992), 199–204.Google Scholar

Mignosi, F. and Restivo, A.. Characteristic Sturmian words are extremal for the critical factorization theorem. Theoret. Comput. Sci. 454 (2012), 199–205.Google Scholar

Mignosi, F., Restivo, A., and Salemi, S.. Periodicity and the golden ratio. Theoret. Comput. Sci. 204 (1998), 153–167.Google Scholar

Mignosi, F., Restivo, A., and Sciortino, M.. Words and forbidden factors. Theoret. Comput. Sci. 273 (2002), 99–117.Google Scholar

Milosevic, M. and Rampersad, N.. Squarefree words with interior disposable factors. Theoret. Comput. Sci. 863 (2021), 120–126.Google Scholar

Mitrofanov, I.. On uniform recurrence of HD0L systems. Arxiv preprint arXiv:1111.1999 [math.CO], available at arxiv.org/abs/1111.1999, 2011.Google Scholar

Mitrofanov, I.. A proof for the decidability of HD0L ultimate periodicity. Arxiv preprint arXiv:1110.4780 [math.CO], available at arxiv.org/abs/1110.4780, 2011.Google Scholar

Mitrofanov, I.. On uniform recurrence of morphic sequences. Arxiv preprint arXiv:1412.5066 [math.CO], available at arxiv.org/abs/1412.5066, 2014.Google Scholar

Mitrofanov, I.. Periodicity of morphic words. J. Math. Sci. 206 (2015), 679–687.Google Scholar

Mitrofanov, I.. On almost periodicity of morphic sequences. Doklady Math. 93 (2016), 207–210.Google Scholar

Mol, L. and Rampersad, N.. Lengths of extremal square-free ternary words. Arxiv preprint arXiv:2001.11763 [math.CO], available at arxiv.org/abs/2001.117 63, 2020.Google Scholar

Mol, L., Rampersad, N., and Shallit, J.. Extremal overlap-free and extremal yS- free binary words. Arxiv preprint arXiv:2006.10152 [math.CO], available at arxiv.org/abs/200 6.10152,2020.Google Scholar

Morse, M.. Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc. 22 (1921), 84–100.Google Scholar

Morse, M. and Hedlund, G. A.. Symbolic dynamics. Amer. J. Math. 60 (1938), 815–866.Google Scholar

Morse, M. and Hedlund, G. A.. Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940), 1–42.Google Scholar

Mousavi, H.. Automatic theorem proving in Walnut. Arxiv preprint arXiv:1603.06017 [cs.FL], available at arxiv.org/abs/1603.0 6017, 2016.Google Scholar

Mousavi, H., Schaeffer, L., and Shallit, J.. Decision algorithms for Fibonacci- automatic words, I: basic results. RAIRO Inform. Theor. App. 50 (2016), 39–66.Google Scholar

Mousavi, H. and Shallit, J.. Mechanical proofs of properties of the Tribonacci word. In Manea, F. and Nowotka, D., editors, Proc. WORDS 2015, Vol. 9304 of Lecture Notes in Computer Science, pp. 1–21. Springer-Verlag, 2015.Google Scholar

Narayanan, S.. Functions on antipower prefix lengths of the Thue-Morse word. Discrete Math. 343 (2020), 111675.Google Scholar

Nathanson, M. B.. Additive Number Theory: The Classical Bases. Springer- Verlag, 1996.Google Scholar

Nicholson, J. and Rampersad, N.. Non-repetitive complexity of infinite words. Disc. Appl. Math. 208 (2016), 114–122.Google Scholar

Nicolas, F. and Pritykin, Yu.. On uniformly recurrent morphic sequences. Internal J. Found. Comp. Sci. 20 (2009), 919–940.Google Scholar

Reyes Noche, J.. On Stewart's choral sequence. Gibon 8(1) (2008), 1–5.Google Scholar

Reyes Noche, J.. Generalized choral sequences. Matimyas Matematika 31 (2008), 25–28.Google Scholar

Reyes Noche, J.. On generalized choral sequences. Gibon 9 (2011), 51–69.Google Scholar

Ochem, P., Rampersad, N., and Shallit, J.. Avoiding approximate squares. Internat. J. Found. Comp. Sci. 19 (2008), 633–648.Google Scholar

Oei, R., Ma, D., Schulz, C., and Hieronymi, P.. Pecan: An automated theorem prover for automatic sequences using Buchi automata. Arxiv preprint arXiv:2102.01727 [cs.LO], available at arxiv.org/abs/2102.01727, 2021.Google Scholar

Ostrowski, A.. Bemerkungen zur Theorie der Diophantischen Approximationen. Abh. Math. Sem. Hamburg 1 (1922), 77-98,250-251. Reprinted in Collected Mathematical Papers, Vol. 3, pp. 57–80.Google Scholar

Pandey, H., Singh, V. K., and Pandey, A.. A new NFA reduction algorithm for state minimization problem. Internat. J. Appl. Info. Sys. 8 (2015), 27–30.Google Scholar

Pansiot, J.-J.. A propos d'une conjecture de F. Dejean sur les repetitions dans les mots. Disc. Appl. Math. 7 (1984), 297–311.Google Scholar

Pansiot, J.-J.. Decidability of periodicity for infinite words. RAIRO Inform. Theor. App. 20 (1986), 43–46.Google Scholar

Parker, E. and Chatterjee, S.. An automata-theoretic algorithm for counting solutions to Presburger formulas. In Duesterwald, E., editor, CC 2004, Vol. 2985 of Lecture Notes in Computer Science, pp. 104–119. Springer-Verlag, 2004.Google Scholar

Peltomaki, J.. Introducing privileged words: privileged complexity of Sturmian words. Theoret. Comput. Sci. 500 (2013), 57–67.Google Scholar

Peltomaki, J.. Privileged factors in the Thue-Morse word—a comparison of privileged words and palindromes. Disc. Appl. Math. 193 (2015), 187–199.Google Scholar

Perrin, D. and Pin, J.-E.. Infinite Words: Automata, Semigroups, Logic and Games, Vol. 141 of Pure and Applied Mathematics. Elsevier, 2004.Google Scholar

Petkovsek, M., Wilf, H. S., and Zeilberger, D.. A = B. A. K. Peters, 1996.Google Scholar

van der Poorten, A. J. and Shallit, J. O.. Folded continued fractions. J. Number Theory 40 (1992), 237–250.Google Scholar

Presburger, M.. Uber die Volstandigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In Sparawozdanie z I Kongresu Matematykow Krajow Slowianskich, pp. 92-101, 395. Sklad Glowny, Warsaw, 1929.Google Scholar

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 12 (1991), 225–233.Google Scholar

Prodinger, H. and Urbanek, F. J.. Infinite 0-1-sequences without long adjacent identical blocks. Discrete Math. 28 (1979), 277–289.Google Scholar

Prouhet, E.. Memoire sur quelques relations entre les puissances des nombres. C. R. Acad. Sci. Paris 33 (1851), 225.Google Scholar

Przybocki, B. P.. Lengths of irreducible and delicate words. Arxiv preprint arXiv:2108.06646 [math.CO], available at arxiv.org/abs/2108.0 664 6, 2021.Google Scholar

Puzynina, S.. Abelian properties of words. In Merca§, R. and Reidenbach, D., editors, WORDS 2019, Vol. 11682 of Lecture Notes in Computer Science, pp. 28–45. Springer-Verlag, 2019.Google Scholar

Puzynina, S. and Zamboni, L. Q.. Abelian returns in Sturmian words. J. Combin. Theory. Ser. A 120 (2013), 390–408.Google Scholar

Rajasekaran, A., Rampersad, N., and Shallit, J.. Overpals, underlaps, and under- pals. In Brlek, S., Dolce, F., Reutenauer, C., and Vandomme, E., editors, WORDS 2017, Vol. 10432 of Lecture Notes in Computer Science, pp. 17–29. Springer-Verlag, 2017.Google Scholar

Rajasekaran, A., Shallit, J., and Smith, T.. Additive number theory via automata theory. Theoret. Comput. Sci. 64 (2020), 542–567.Google Scholar

Ramlrez-Alfonsln, J. L.. The Diophantine Frobenius Problem. Oxford University Press, 2005.Google Scholar

Rampersad, N.. The periodic complexity function of the Thue-Morse word, the Rudin-Shapiro word, and the period-doubling word. Arxiv preprint arXiv:2112.04416 [math.CO], available at arxiv.org/abs/2112.04416, 2021.Google Scholar

Rampersad, N., Rigo, M., and Salimov, P.. A note on abelian returns in rotation words. Theoret. Comput. Sci. 528 (2014), 101–107.Google Scholar

Rampersad, N., Shallit, J., and Vandomme, E.. Critical exponents of balanced words. Theoret. Comput. Sci. 777 (2019), 454–463.Google Scholar

Rampersad, N., Shallit, J., and Wang, M.-w.. Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005), 19–34.Google Scholar

Reble, D.. Zeckendorf vs. Wythoff representations: comments on A007895. Manuscript available at oeis.org/A0 078 95/a0078 95.pdf, 2008.Google Scholar

Riasat, S.. Powers and anti-powers in binary words. Master's thesis, University of Waterloo, Waterloo, Ontario, Canada, 2019. Available at tinyurl.com/2pbzumf6.Google Scholar

Richomme, G., Saari, K., and Zamboni, L. Q.. Abelian complexity in minimal subshifts. J. LondonMath. Soc. 83 (2011), 79–95.Google Scholar

Rigo, M.. Formal Languages, Automata and Numeration Systems 1: Introduction to Combinatorics on Words. Wiley, 2014.Google Scholar

Rigo, M.. Formal Languages, Automata and Numeration Systems 2: Applications to Recognizability and Decidability. Wiley, 2014.Google Scholar

Rigo, M., Salimov, P., and Vandomme, E.. Some properties of abelian return words. J. Integer Sequences 16 (2013), Article 13.2.5 (electronic). Available at cs.uwaterloo.ca/journals/JIS/VOL16/Rigo/rigo3.html.Google Scholar

Rigo, M. and Waxweiler, L..A note on syndeticity, recognizable sets and Cob- ham's theorem. Bull. European Assoc. Theor. Comput. Sci., No. 88, (2006), 169–173.Google Scholar

Robbins, N.. Fibonacci partitions. Fibonacci Quart. 34 (1996), 306–313.Google Scholar

Robson, J. M.. Separating strings with small automata. Inform. Process. Lett. 30 (1989), 209–214.Google Scholar

Robson, J. M.. Separating words with machines and groups. RAIRO Inform. Theor. App. 30 (1996), 81–86.Google Scholar

Rowland, E. and Shallit, J.. k-automatic sets of rational numbers. In Dediu, A. H. and Martin-Vide, C., editors, Languages and Automata Theory and Applications—6th International Conference, LATA 2012, Vol. 7183 of Lecture Notes in Computer Science, pp. 490–501. Springer-Verlag, 2012.Google Scholar

Rowland, E. and Shallit, J.. Automatic sets of rational numbers. Internat. J. Found. Comp. Sci. 26 (2015), 343–365.Google Scholar

Roy, A. and Straubing, H.. Definability of languages by generalized first-order formulas over (N, +). SIAM J. Comput. 37 (2007), 502–521.Google Scholar

Rudin, W.. Some theorems on Fourier coefficients. Proc. Amer. Math. Soc. 10 (1959), 855–859.Google Scholar

Saari, K.. Periods of factors of the Fibonacci word. In WORDS 07, 2007.Google Scholar

Salon, O.. Suites automatiques a multi-indices. In Seminaire de Theorie des Nombres de Bordeaux, pp. 4.01-4.27, 1986–1987.Google Scholar

Salon, O.. Suites automatiques a multi-indices et algebricite. C. R. Acad. Sci. Paris 305 (1987), 501–504.Google Scholar

Salon, O.. Quelles tuiles! (pavages aperiodiques du plan et automates bidimen- sionnels). Seminaire de Theorie des Nombres de Bordeaux 1 (1989), 1–25.Google Scholar

Salon, O.. Proprietes arithmetiques des automates multidimensionnels. PhD thesis, Universite Bordeaux I, 1989.Google Scholar

Sandor, C.. Partitions of natural numbers and their representation functions. INTEGERS—Elect. J. Comb. Numb. Theory 4 (2004), #A18.Google Scholar

Schaeffer, L.. Deciding properties of automatic sequences. Master's thesis, School of Computer Science, University of Waterloo, 2013.Google Scholar

Schaeffer, L. and Shallit, J.. The critical exponent is computable for automatic sequences. Internat. J. Found. Comp. Sci. 23 (2012), 1611–1626.Google Scholar

Schaeffer, L. and Shallit, J.. Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences. Electron. J. Combin. 23(1) (2016), #P1.25 (electronic).Google Scholar

Schaeffer, L. and Shallit, J.. String attractors for automatic sequences. Arxiv preprint arXiv:2012.06840 [cs.FL], available at arxiv.org/abs/2012.06840, 2021.Google Scholar

Schlage-Puchta, J.-C.. A criterion for non-automaticity of sequences. J. Integer Sequences 6 (2003), Article 03.3.8 (electronic). Available at tinyurl.com/5ppysyct.Google Scholar

Schmitz, S.. Complexity hierarchies beyond elementary. ACM Trans. Comput. Theory 8(1) (2016), Article 3.Google Scholar

Schule, T.. Verification of Infinite State Systems Using Presburger Arithmetic. PhD thesis, Fachbereich Informatik, Technischen Universitat Kaiserslautern, 2007.Google Scholar

Schweikardt, N.. Arithmetic, first-order logic, and counting quantifiers. ACM Trans. Comput. Logic 6 (2005), 634–671.Google Scholar

Seebold, P.. Proprietes combinatoires des mots infinis engendres par certains morphismes (These de 3^e cycle). PhD thesis, Universite P. et M. Curie, Institut de Programmation, Paris, 1985.Google Scholar

Seebold, P.. Lyndon factorization of the Prouhet words. Theoret. Comput. Sci. 307 (2003), 179–197.Google Scholar

Shallit, J. O.. Simple continued fractions for some irrational numbers. J. Number Theory 11 (1979), 209–217.Google Scholar

Shallit, J. O.. Numeration systems, linear recurrences, and regular sets. Inform. Comput. 113 (1994), 331–347.Google Scholar

Shallit, J.. A Second Course in Formal Languages and Automata Theory. Cambridge University Press, 2009.Google Scholar

Shallit, J.. The critical exponent is computable for automatic sequences. In P. Ambroz, S. Holub, and Z. Masakova, editors, WORDS 2011, 8th International Conference, pp. 231-239. Elect. Proc. Theor. Comput. Sci., 2011. Revised version, with L. Schaeffer, available at arxiv.org/abs/1104.2303v2.Google Scholar

Shallit, J.. Enumeration and automatic sequences. Pure Math. Appl. 25 (2015), 96–106.Google Scholar

Shallit, J.. Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture. Indag. Math. 32 (2021), 729–735.Google Scholar

Shallit, J.. Frobenius numbers and automatic sequences. Arxiv preprint arXiv:2103.10904 [math.NT], available at arxiv.org/abs/2103.10 904, 2021.Google Scholar

Shallit, J.. Hilbert's spacefilling curve described by automatic, regular, and synchronized sequences. Arxiv preprint arXiv:2106.01062 [cs.FL], available at arxiv.org/abs/210 6.010 62, 2021.Google Scholar

Shallit, J.. Robbins and Ardila meet Berstel. Inform. Process. Lett. 167 (2021), 106081.Google Scholar

Shallit, J.. Abelian complexity and synchronization. INTEGERS—Elect. J. Comb. Numb. Theory 21 (2021), #A36 (electronic). Available at tinyurl.com/3 6ba7eza.Google Scholar

Shallit, J.. Additive number theory via automata and logic. Arxiv preprint arXiv:2112.13627 [math.NT], available at arxiv.org/abs/2112.13627, 2021.Google Scholar

Shallit, J.. Synchronized sequences. In Lecroq, T. and Puzynina, S., editors, WORDS 2021, Vol. 12847 of Lecture Notes in Computer Science, pp. 1–19. Springer-Verlag, 2021.Google Scholar

Shallit, J.. Sumsets of Wythoff sequences, Fibonacci representation, and beyond. Period. Math. Hung. 84 (2022), 37–46.Google Scholar

Shallit, J.. Note on a Fibonacci parity sequence. Arxiv preprint arXiv:2203.10504 [cs.FL]. Available at arxiv.org/abs/2203.10504, 2022.Google Scholar

Shallit, J. O. and Wang, M.-w.. Weakly self-avoiding words and a construction of Friedman. Electron. J. Combin. 8(1) (2001), N2 (electronic), tinyurl.com/bmhsns5 6Google Scholar

Shallit, J. and Zarifi, R.. Circular critical exponents for Thue-Morse factors. RAIRO Inform. Theor. App. 53 (2019), 37–49.Google Scholar

Shapiro, H.S.. Extremal problems for polynomials and power series. Master's thesis, MIT, 1952.Google Scholar

Shur, A. M.. Combinatorial complexity of rational languages. Diskretn. Anal. Issled. Oper, Ser. 1 12(2) (2005), 78–99. In Russian.Google Scholar

Shur, A.. Growth properties of power-free languages. Comput. Sci. Rev. 6 (2012), 187–208.Google Scholar

Sipser, M.. Introduction to the Theory of Computation. Cengage Learning, 3rd edition, 2013.Google Scholar

Siromoney, R., Mathew, L., Dare, V., and Subramanian, K.. Infinite Lyndon words. Inform. Process. Lett. 50 (1994), 101–104.Google Scholar

Sloane, N. J. A. et al. The On-Line Encyclopedia of Integer Sequences, 2022. Available at oeis.org.Google Scholar

Sprunger, D., Tune, W., Endrullis, J., and Moss, L. S.. Eigenvalues and transduction of morphic sequences. In Shur, A. M. and Volkov, M. V., editors, Developments in Language Theory, 18th International Conference, DLT 2014, Vol. 8633 of Lecture Notes in Computer Science, pp. 239–251. Springer-Verlag, 2014.Google Scholar

Stewart, I.. How to Cut a Cake: And Other Mathematical Conundrums. Cambridge University Press, 2006.Google Scholar

Subrahmonian Moothatu, T. K.. Eulerian entropy and non-repetitive subword complexity. Theoret. Comput. Sci. 420 (2012), 80–88.Google Scholar

Sun, Z. and Winterhof, A.. On the maximum order complexity of the Thue-Morse and Rudin-Shapiro sequence. Uniform. Distrib. Theory 14 (2019), 33–42.Google Scholar

Szilard, A., Yu, S., Zhang, K., and Shallit, J. O.. Characterizing regular languages with polynomial densities. In Havel, I. M. and Koubek, V., editors, Proc. 17th Symposium, Mathematical Foundations of Computer Science 1992, Vol. 629 of Lecture Notes in Computer Science, pp. 494–503. Springer-Verlag, 1992.Google Scholar

Tang, M.. Partitions of the set of natural numbers and their representation functions. Discrete Math. 308 (2008), 2614–2616.Google Scholar

Tan, B. and Wen, Z.-Y.. Some properties of the Tribonacci sequence. European J. Combin. 28 (2007), 1703–1719.Google Scholar

Thue, A.. Uber unendliche Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), 1-22. Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 139–158.Google Scholar

Thue, A.. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), 1-67. Reprinted in Selected Mathematical Papers ofAxel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 413–478.Google Scholar

Turek, O.. Abelian complexity function of the Tribonacci word. J. Integer Sequences 18 (2015), Article 15.3.4 (electronic). Available at tinyurl.com/mr2xuv3p.Google Scholar

Vajda, S.. Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications. Dover, 2007.Google Scholar

Valmari, A.. Fast brief practical DFA minimization. Inform. Process. Lett. 112 (2012), 213–217.Google Scholar

Wah, A. and Picciotto, H.. Algebra: Themes, Tools, Concepts. Creative Publications, Mountain View, CA, 1994. Available at tinyurl.com/bdpbt6m6.Google Scholar

White, T.. On the coefficients of a recursion relation for the Fibonacci partition function. Fibonacci Quart. 24 (1986), 133–137.Google Scholar

Widmer, S.. Permutation complexity of the Thue-Morse word. Adv. in Appl. Math. 47 (2011), 309–329.Google Scholar

Wilf, H.. What is an answer? Amer. Math. Monthly 89 (1982), 289–292.Google Scholar

Wythoff, W. A.. A modification of the game of nim. Nieuw Archiefvoor Wiskunde 7 (1907), 199–202.Google Scholar

Zeckendorf, E.. Representation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. Roy. Liege 41 (1972), 179–182.Google Scholar

Book contents

Bibliography

Summary

Access options

References

Book contents

Bibliography

Summary

Access options

References

Save book to Kindle

Save book to Dropbox

Save book to Google Drive