Selected works of Jeffrey O. Shallit

I grant readers of this page the right to reproduce one copy of any paper on this page for the purposes of research and self-study.

A star (*) next to the authors' name indicates that we have used an LLM to obtain some or all of the results in the paper.

DOI links will work if you or your institution have a subscription to the journal.

A partial list of my co-authors is here.

• 2026
  • * Stijn Cambie, Erik Kalviainen, and J. Shallit, Brown-Gerver-Ramsey Theorems in Small Dimensions, Arxiv preprint arXiv:2609.20366 [math.CO], September 17 2026. Also see a visualization here.
  • * Rastko Maslic and J. Shallit, Solution to Bucher's density problem for context-free languages, arXiv:2609.08571 [cs.FL], September 8 2026.
  • * J. Shallit, An infinite walk in N¹⁶, using only unit steps, with no three collinear points, arxiv preprint arXiv:2609.05780 [math.CO], September 5 2026.
    • Note: the theorem in this paper has been completely superseded by the results in Cambie et al. above.
  • * G. Caveney, H. Dong, and J. Shallit, Repetition avoidance in curling number transforms, Arxiv preprint arXiv:2608.15670 [math.CO], August 16 2026. Available at https://arxiv.org/abs/2608.15670.
  • D. Moradi, N. Rampersad, and J. Shallit, Complexity of Linear Subsequences of k-Automatic Sequences, in T. J. Smith, ed., CIAA 2026, Lect. Notes in Comp. Sci., Vol. 16695, Springer, 2026, pp. 185-199.
  • * J. Shallit, Palindrome complexity versus factor complexity, Arxiv preprint arXiv:2606.08127 [math.CO], June 6 2026. Available at https://arxiv.org/abs/2606.08127.
  • * J. Shallit, Ten squares force an overlap, Arxiv preprint arXiv:2605.28570 [math.CO], May 27 2026. Available at https://arxiv.org/abs/2605.28570.
  • M. Alexeev, T. Amdeberhan, J. Shallit, and I. Vukusic, On the p-adic valuations of values of Legendre polynomials, Res. Number Theory (2026) 12:52.
  • * Jeffrey Shallit, Brik's sequence: a strange recursion, Arxiv preprint arXiv:2605.07542 [math.CO], May 8 2026. Available at https://arxiv.org/abs/2605.07542.
  • Jozef Jirásek, Galina Jirásková, and Jeffrey Shallit, State complexity of the minimal star basis, Theor. Comput. Sci. 1073 (2026), 115892.
  • J. Shallit and E. Vandomme, Running maximum of a k-regular sequence, Info. Proc. Letters 194 (2026), 106641.
  • * J. Shallit, The speed of convergence in greedy Galois games, Arxiv preprint arXiv:2605.00194 [cs.FL], April 30 2026. Available at https://arxiv.org/abs/2605.00194.
  • L. Schaeffer, J. Shallit, and S. Zorcic, Beatty sequences for a quadratic irrational: decidability and applications, Discrete Math. 349 (2026), 115183.
  • J. Shallit and I. Vukusic, Balanced Fibonacci word rectangles, and beyond, Discrete Math. Theoret. Comput. Sci. 28 (2) (2026).
  • Delaram Moradi, Narad Rampersad, and Jeffrey Shallit, Complexity of linear subsequences of Fibonacci-automatic sequences, Arxiv preprint arXiv:2603.21645 [cs.FL], March 23 2026.
  • Lubomíra Dvořáková, Edita Pelantová, and Jeffrey Shallit, On a sequence of Kimberling and its relationship to the Tribonacci word, Discrete Mathematics and Theoretical Computer Science, 28 (2) (2026), Paper #19. Available at https://dmtcs.episciences.org/17782.
  • Delaram Moradi, Pierre Popoli, Jeffrey Shallit, and Ingrid Vukusic, State complexity of shifts of the Fibonacci word, Arxiv preprint arXiv:2603.18858 [cs.FL], March 19 2026. Available at https://arxiv.org/abs/2603.18858. Conference version, in C. Campeanu et al., eds., DCFS 2026, Lect. Notes in Comp. Sci., Vol. 16681, Springer, 2026, pp. 133-147.
  • Jeffrey Shallit, Prefixes of the Fibonacci word, Theoret. Comput. Sci. (2026).
  • Jeffrey Shallit, Runs in paperfolding sequences, J. Austral. Math. Soc. 113 (2) (2026), 216-230. Available at https://doi.org/10.1017/S0004972725100440.
  • Aaron Barnoff, Curtis Bright, and Jeffrey Shallit, Computing the base-b representation of quadratic irrationals using automata, Theoret. Comput. Sci. 1071 (2026), 115843. Available at https://doi.org/10.1016/j.tcs.2026.115843.
  • Christophe Reutenauer and Jeffrey Shallit, Christoffel matrices and Sturmian determinants, RAIRO Informatique Théorique 60 (2026), 6.
  • Benoit Cloitre and Jeffrey Shallit, A self-generating sequence, Theoretical Computer Science 1066 (2026), 115721. Available at https://doi.org/10.1016/j.tcs.2025.115721.
  • Benoit Cloitre and Jeffrey Shallit, Some Fibonacci-related sequences, Fibonacci Quarterly, 2026. Available at https://doi.org/10.1080/00150517.2025.2487802.

• 2025
  • Delaram Moradi, Narad Rampersad, and Jeffrey Shallit, Complexity of linear subsequences of k-automatic sequences, Arxiv preprint arXiv:2512.10017 [cs.FL], December 10 2025.
  • Lubomíra Dvořáková, Edita Pelantová, and Jeffrey Shallit, On a sequence of Kimberling and its relationship to the Tribonacci word, Arxiv preprint arXiv:2510.11318 [math.CO], October 13 2025.
  • Jeffrey Shallit, The Tribonacci constant and finite automata, Arxiv preprint arXiv:2510.10834 [cs.FL], October 12 2025.
  • J. Shallit and I. Vukusic, Balanced Fibonacci word rectangles, and beyond, Arxiv preprint arXiv:2509.25994 [math.NT], September 30 2025.
    • tar file containing a list of all the Walnut commands, a copy of the Walnut files for the automata called maxval.txt and tmbal.txt (which are hard to compute), and the Maple files cnt6a.mpl, cnt6b.mpl, and numfib6.mpl, and the Maple file minimize.mpl for minimizing linear representations.
  • M. Khodier, L. Schaeffer, and J. Shallit, Self-verifying predicates in Büchi arithmetic, Arxiv preprint arXiv:2507.19717 [cs.FL], July 25 2025. Conference version in Self-verifying predicates in Büchi arithmetic, in G. Castiglione and S. Mantaci, eds., CIAA 2025, Lect. Notes in Comp. Sci., Vol. 15981, Springer, 2026, pp. 237-251.
  • Jeffrey Shallit and Ingrid Vukusic, New properties of the ϕ-representation of integers, Arxiv preprint arXiv:2509.16150 [math.NT], September 19 2025.
  • Jean-Paul Allouche, John M. Campbell, Shuo Li, Jeffrey Shallit, and Manon Stipulanti, The reflection complexity of sequences over finite alphabets, Theory of Computing Systems 69 (2025), Article 31. another link.
    Note 1: some of the conjectures in our paper have recently been resolved by Dvořáková and Pelantová in https://arxiv.org/abs/2511.12358.
    Note 2: Our Remark 10 reads "Also note that if a sequence x is uniformly recurrent and contains infinitely many distinct palindromes, then x is reversal-closed [15, Theorem 3.2]." It happens that this (easy) remark is already (at least) in a paper of Bo Tan (Theoretical Computer Science 389 (2007) 118–124) where this is Proposition 3.1 (he calls "palindromic" all infinite sequence having infinitely many distinct palindromes). We should have cited that, too.
    
  • Gabriele Fici, Jeffrey Shallit, and Jamie Simpson. On Palindromic Periodicities. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025). Available at https://doi.org/10.4230/LIPIcs.CPM.2025.11.
  • Max A. Alekseyev, Tewodros Amdeberhan, Jeffrey Shallit, Ingrid Vukusic, On the p-adic valuations of values of Legendre polynomials, arxiv preprint arXiv:2505.08935 [math.NT], May 13 2025.
  • Jean-Michel Couvreur, Martin Delacourt, Nicolas Ollinger, Pierre Popoli, Jeffrey Shallit, and Manon Stipulanti, Effective Computation of Generalized Abelian Complexity for Pisot Type Substitutive Sequences, ArXiv preprint arXiv:2504.13584 [cs.FL].
  • Narad Rampersad, Jeffrey Shallit, and Xinhao Xu, Repetition factorization of automatic sequences, Int'l. J. Found. Comput. Sci. 36 (2025), 479-499.
  • Jeffrey Shallit, Proving Properties of ϕ-Representations with the Walnut Theorem-Prover, Commun. Math. 33 (2) (2025), Paper 3.
  • Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences Discrete Math. 348 (2025), 114487.
  • Jeffrey Shallit, The Narayana morphism and related words, ArXiv preprint arXiv:2503.01026 [math.CO], March 2 2025. Accepted by Bull. Inst. Combin. Appl.; see here. Files for the paper:
    • naranum.tar, uncompress and put in the "Custom Bases" directory of Walnut
    • naracode.tar, uncompress and put in the "Automata Library" directory of Walnut
  • Jeffrey Shallit, An 'Experimental Mathematics' Approach to Stolarsky Interspersions via Automata Theory, ArXiv preprint arXiv:2502.03312 [cs.FL], February 5 2025. Available at https://arxiv.org/abs/2502.03312.
    • automata for the paper
  • Narad Rampersad and Jeffrey Shallit, Rudin-Shapiro sums via automata theory and logic, Theor. Comput. Sys. 69 (2025), Article 9.
    • Walnut code for the paper
    • RS4.txt; put this in the Word Automata Library of Walnut
    • rss.txt; put this in the Automata Library of Walnut
    • rst.txt; put this in the Automata Library of Walnut
  • Jeffrey Shallit, The Hurt-Sada array and Zeckendorf representations, arxiv preprint arXiv:2501.08823 [math.NT], January 15 2025. To verify the results in the paper, uncompress the following file and put the four automata in the Automata Library directory of Walnut:
    • wal.tar
    You can also cut-and-paste from the following file of all the Walnut commands in the paper.
    • sada-walnut2.txt
  • Jeffrey Shallit, Cloitre's self-generating sequence, arXiv preprint arXiv:2501.00784 [math.CO], January 1 2025. To verify the results in the paper, put the following automata in the Automata Library directory of Walnut:
    • e.txt
    • ep.txt
    • g.txt
    and this one in the Word Automata Library:
    • Q.txt
  • Lucas Mol, Narad Rampersad, Jeffrey Shallit, Dyck words, pattern avoidance, and automatic sequences, Communications in Mathematics 33 (2025) (2), Paper no. 5.

• 2024
  • J. Shallit, A. Shur, and S. Zorcic, Power-free complementary binary morphisms, J. Combin. Theory, Ser. A 207 (2024), 105910.
  • Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, and Jeffrey Shallit, Decidability for Sturmian words, Logical Methods in Computer Science 20 (3) (2024), 12:1-12:38.
  • J. Shallit, Runs in paperfolding sequences, ArXiv preprint arXiv:2412.17930 [math.CO], December 23 2024. To verify the results with Walnut, put the following automata in the Automata Library of Walnut.
    • sp.txt
    • assoc.txt
  • N. Rampersad, J. Shallit, and Xinhao Xu, Repetition factorization of automatic sequences, Int. J. Found. Comput. Sci., 2024.
  • J. Currie, L. Mol, N. Rampersad, and J. Shallit, Extending Dekking's construction of an infinite binary word avoiding abelian 4-powers, SIAM J. Discrete Math. 38 (2024), 2913-2925. Available at http://doi.org/10.1137/23M1558513.
  • Pierre Popoli, Jeffrey Shallit, Manon Stipulanti, Additive word complexity and Walnut, ArXiv preprint arXiv:2410.02409 [math.CO], October 3 2024.
  • Christophe Reutenauer, Jeffrey Shallit, Christoffel Matrices and Sturmian Determinants, ArXiv preprint arXiv:2409.09824 [math.CO], September 15 2024.
  • Gabriele Fici, Jeffrey Shallit, Jamie Simpson, Some remarks on palindromic periodicities, ArXiv preprint arXiv:2407.10564 [math.CO], July 15 2024. Available at https://arxiv.org/abs/2407.10564.
  • Nicolas Ollinger, Jeffrey Shallit, The repetition threshold for Rote sequences, Arxiv preprint arXiv:2406.17867 [math.CO], June 25 2024. Available at https://arxiv.org/abs/2406.17867. There is some supplementary material, including
    • An html file with more information about the computations
    • A Jupyter notebook explaining what we did
  • Jean-Paul Allouche, John M. Campbell, Shuo Li, Jeffrey Shallit, Manon Stipulanti, The reflection complexity of sequences over finite alphabets, Arxiv preprint arXiv:2406:09302 [math.CO], June 13 2024. Available at https://arxiv.org/abs/2406.09302. Current version is dated May 6 2025.
  • J.-P. Allouche, N. Rampersad, and J. Shallit, Repetition threshold for binary automatic sequences, Arxiv preprint arXiv:2406.06513 [math.CO], June 10 2024. Available at https://arxiv.org/abs/2406.06513. To check the claims of the paper, you can use the following Walnut code.
    • Code for checking that the morphisms in Table 1 generate squarefree words by iteration: ARS-table1.txt
    • Code for checking cases k = 3,6 in Table 2: ARS-table2.txt
    • Fibonacci DFAO in Figure 1 to compute the sequence y, put this in the Word Automata directory of Walnut: Y2.txt
    • Code for checking squarefreeness of y and computing h(y) in Remark 12: ARS-remark12.txt
    • Fibonacci DFAO for the word w in Remark 12, put this in the Word Automata directory of Walnut: W.txt
    • Walnut code checking (7/3)-freeness of w: ARS-remark12b.txt
    • Tribonacci DFAO for the word z in Theorem 13, put this in the Word Automata directory of Walnut: Z.txt
    • Walnut code for the DFAO for h(z): ARS-thm13.txt
  • J. Shallit, Proof of Irvine's conjecture by mechanized guessing, INTEGERS 24 (2024), Paper #A51. Available at https://math.colgate.edu/~integers/y51/y51.pdf.
  • Aaron Barnoff, Curtis Bright, and Jeffrey Shallit, Using finite automata to compute the base-b representation of the golden ratio and other quadratic irrationals, Arxiv preprint arXiv:2405.02727 [cs.FL], May 4 2024. Available at https://arxiv.org/abs/2405.02727. To appear, Proc. CIAA 2024, LNCS 15015, Springer, 2024.
  • Jason Bell, Chris Schulz, and Jeffrey Shallit, Consecutive power occurrences in Sturmian words, Arxiv preprint arXiv:2402.09597 [math.CO], February 14 2024. Available at https://arxiv.org/abs/2402.09597.
  • Luke Schaeffer, Jeffrey Shallit, and Stefan Zorcic, Beatty Sequences for a Quadratic Irrational: Decidability and Applications, Arxiv preprint arXiv:2402.08331 [math.NT], February 13 2024. Available at https://arxiv.org/abs/2402.08331. For the automata used in this paper, download this tar file, untar it, and put all the files in the Automata Library directory of Walnut.
  • Daniel Krenn and Jeffrey Shallit, Strongly k-recursive sequences, Arxiv preprint arXiv:2401.14231 [cs.FL], January 25 2024. Available at https://arxiv.org/abs/2401.14231.
  • Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, Arxiv preprint arXiv:2401.13524 [math.CO], January 24 2024. Available at https://arxiv.org/abs/2401.13524.
  • Ali Keramatipour and Jeffrey Shallit, Record-setters in the Stern sequence, Discrete Math. 347 (2024), 113852. Available at https://doi.org/10.1016/j.disc.2023.113852.
  • Jeffrey Shallit, Proving properties of some greedily-defined integer recurrences via automata theory, Theoret. Comput. Sci. 988 (2024), 114363.
    • tar file with all the automata and commands needed in the paper
  • Jeffrey Shallit, Rarefied Thue-Morse sums via automata theory and logic, J. Number Theory 257 (2024) 98-111.
  • J.-P. Allouche and J. Shallit, Additive properties of the evil and odious numbers and similar sequences, Funct. Approx. Comment. Math. 70 (1) (2024), 55-69.
  • L. Schaeffer and J. Shallit, The first-order theory of binary overlap-free words is decidable, Canad. J. Math. 76 (2024), 1144-1162.
    • There is a small error in the statement of Theorem 5.5. It refers to all overlap-free words, but the theorem is actually about all overlap-free Restivo words.
    • The definition for `normalize' was omitted. You can download it here: normalize.txt.
    • The definition for `CODE' was omitted. You can download it here: CODE.txt.

• 2023
  • Jeffrey Shallit, When the world's "wrongest" mathematician was arrested in Kitchener, Waterloo Historical Society J. 111 (2023), 75-81.
  • Jeffrey Shallit, Some Tribonacci conjectures, Fibonacci Quart. 61 (2023), no. 3, 214–221.
  • Benoit Cloitre and Jeffrey Shallit, Some Fibonacci-Related Sequences, arXiv preprint arXiv:2312.11706 [math.CO], December 18 2023. Available at https://arxiv.org/abs/2312.11706.
  • J. Shallit and X. Xu, Repetition factorization of automatic sequences, Arxiv preprint arXiv:2311.14961 [cs.FL], November 25 2023. Available at https://arxiv.org/abs/2311.14961.
  • J. Shallit, A. M. Shur, and S. Zorcic, New constructions for 3-free and 3⁺-free binary morphisms. Arxiv preprint arXiv:2310.15064 [math.CO], October 23 2023.
    Walnut files for the paper:
    • Walnut commands for section 3 of the paper
    • Walnut commands for section 4 of the paper
    • Walnut commands for section 5 of the paper
    • X.txt, put in the Word Automata directory of Walnut
    • Y.txt, put in the Word Automata directory of Walnut
    • tar file of automata produced, unpack and put in the Automata Library directory of Walnut. These will be produced by the commands above if you have enough RAM on your machine and time to devote (about two weeks of computation time on a machine with 400G of RAM). But if you do not have this time you can just work with the automata produced.
  • J. Shallit, Proof of Irvine's conjecture via mechanized guessing, Arxiv preprint arXiv:2310.14252 [math.CO], October 22 2023.
    Files for the paper:
    • K.txt, put this in the "Word Automata Library" directory of Walnut.
    • files for numeration system, unpack and put both files in the "Custom Bases" directory of Walnut.
    • files for the sequences, unpack and put all these files in the "Automata Library" of Walnut.
  • J. Shallit, Proving Results About OEIS Sequences with Walnut, in C. Dubois and M. Kerber, eds., CICM 2023, LNAI Vol. 14101, Springer, 2023, pp. 270-282.
  • Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic words and a question of Shevelev, Discrete Math. Theoret. Comput. Sci. 25(2) (2023), Paper No. 6. Available at https://doi.org/10.46298/dmtcs.9919.
  • Aseem Baranwal, James Currie, Lucas Mol, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, Antisquares and critical exponents, Discrete Math. Theoret. Comput. Sci. 25(2) (2023), Paper #11.
  • J. Shallit, Note on a Fibonacci parity sequence, Cryptography and Communications 15 (2023), 309-315.
  • J. Shallit and S. L. Shan, A general approach to proving properties of Fibonacci representations via automata theory, in Z. Gazdag, S. Iván and G. Kovásznai, eds., AFL 2023, Electronic Proceedings in Theoretical Computer Science 386 (2023), 228-242. Available at here.
  • J. Shallit, Proving properties of some greedily-defined integer recurrences via automata theory. Arxiv preprint arXiv:2308.06544 [cs.DM], August 12 2023, available at https://arxiv.org/abs/2308.06544.
    • tar file with all the automata and commands needed in the paper
  • D. Badziahin and J. Shallit, Badly approximable numbers, Kronecker's theorem, and diversity of Sturmian characteristic sequences, J. Théorie Nombres Bordeaux 35 (2023), 1-15.
  • J. Shallit, Proving Properties of ϕ-Representations with the Walnut theorem-prover, arxiv preprint arXiv:2305.02672 [math.NT], May 4 2023. Available at https://arxiv.org/abs/2305.02672.
    • All of the automata needed
    • Maple files for matrices
  • J. Shallit, S. L. Shan and K. H. Yang, Automatic sequences in negative bases and proofs of some conjectures of Shevelev, RAIRO-Théor. Inf. Appl. 57 (2023), 4.
  • J. Shallit and A. Zavyalov, Transduction of automatic sequences and applications, arxiv preprint arXiv:2303.15203 [cs.FL], March 27 2023. Available at https://arxiv.org/abs/2303.15203. Conference version appeared in B. Nagy, ed., CIAA 2023, LNCS 14151, pp. 266-277, 2023 here: https://doi.org/10.1007/978-3-031-40247-0_20.
  • J. P. Bell and J. Shallit, Counterexamples to a conjecture of Dombi in additive number theory, Acta Math. Hung. 169 (2023) 562-565. Available at https://doi.org/10.1007/s10474-023-01312-y. Corrigendum: the definition of the forbidden set F should be {4ⁿ⁺¹: n ≥ 0}.
  • James Currie, L'ubomíra Dvořaková, Pascal Ochem, Daniela Opočenská, Narad Rampersad, and Jeffrey Shallit, Complement avoidance in binary words, arxiv preprint arXiv:2209.09598v2 [math.CO], March 12 2023. A revision of the paper from 2022 below, with two new co-authors, and the problem completely resolved.
  • Daniel Gabric and Jeffrey Shallit, Smallest and largest block palindrome factorizations, Arxiv preprint arXiv:2302.13147 [math.CO], March 6 2023. An abbreviated version of this paper appeared in A. Frid and R. Mercas, eds., WORDS 2023, LNCS 13899, Springer, 2023, pp. 181-191.
  • Jeffrey Shallit, Rarefied Thue-Morse Sums Via Automata Theory and Logic, Arxiv preprint ArXiv:2302.09436 [math.NT], February 18 2023.
    • f30.txt -- f30.txt, put this in the "Automata Library" directory of Walnut
    • f31.txt -- f31.txt, put this in the "Automata Library" directory of Walnut
    • f32.txt -- f32.txt, put this in the "Automata Library" directory of Walnut
    • f50.txt -- f50.txt, put this in the "Automata Library" directory of Walnut
    • f51.txt -- f51.txt, put this in the "Automata Library" directory of Walnut
    • conv55.txt -- conv55.txt, put this in the "Automata Library" directory of Walnut
    • moser-walnut-cmds.txt, all the Walnut commands in the paper
  • Jeffrey Shallit, Prefixes of the Fibonacci word, Arxiv preprint arXiv:2302.04640 [cs.FL], February 9 2023.
    • Walnut code for the paper
  • Jeffrey Shallit, A Dombi counterexample with positive lower density, Arxiv preprint arXiv:2302.02138 [math.NT], February 4 2023. Final revised version appeared in INTEGERS 23 (2023), #A74, and available here.
  • Narad Rampersad and Jeffrey Shallit, Rudin-Shapiro sums via automata theory and logic, Arxiv preprint arXiv:2302.00405 [math.NT], February 1 2023.
    • Walnut code for the paper
    • RS4.txt; put this in the Word Automata Library of Walnut
    • rss.txt; put this in the Automata Library of Walnut
    • rst.txt; put this in the Automata Library of Walnut
    An abbreviated version of this paper appeared in A. Frid and R. Mercas, eds., WORDS 2023, LNCS 13899, Springer, 2023, pp. 233-246. Paper is available here.
  • Jeffrey Shallit, Proof of a conjecture of Krawchuk and Rampersad, arxiv preprint arXiv:2301.11473 [math.CO], January 27 2023. Preprint at https://arxiv.org/abs/2301.11473. Final version appeared as Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence, INTEGERS 23 (2023), #A44.
  • Lucas Mol, Narad Rampersad, Jeffrey Shallit, Dyck words, pattern avoidance, and automatic sequences, arxiv preprint arXiv:2301.06145 [cs.DM], January 15 2023. Available at https://arxiv.org/abs/2301.06145. An abbreviated version of this paper appeared in A. Frid and R. Mercas, eds., WORDS 2023, LNCS 13899, Springer, 2023, pp. 220-232.
    • typo: The invocation of 'tmfac1' on page 227, Example 11, should have been N1.
  • Robert Cummings, Jeffrey Shallit, Paul Staadecker, Mesosome avoidance, Info. Proc. Letters 179 (2023), 106291.
  • James Currie, Pascal Ochem, Narad Rampersad and Jeffrey Shallit, Properties of a ternary infinite word, RAIRO-Théor. Inf. Appl. 57 (2023). Available at https://www.rairo-ita.org/articles/ita/abs/2023/01/ita220038/ita220038.html.

• 2022
  • Carlo Sanna, Jeffrey Shallit, Shun Zhang, The largest entry in the inverse of a Vandermonde matrix Linear Multilin. Alg. 70 (2022), 5634-5641.
  • Jason P. Bell and Jeffrey Shallit, Counterexample to a conjecture of Dombi in additive number theory, Arxiv preprint arXiv:2212.12473 [math.NT], December 28 2022.
  • Jeffrey Shallit, The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words with Walnut, London Math. Soc. Lecture Note Series, Vol. 482, Cambridge University Press, September 29 2022.
  • Jeffrey Shallit, Some Tribonacci conjectures, arxiv preprint arXiv:2210.03996 [math.CO], October 8 2022. Here are the files for the automata you will need in this paper. Put them in the "Automaton Library" of Walnut.
    • xaut.txt
    • yaut.txt
  • James Currie, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, Complement avoidance in binary words, arxiv preprint arXiv:2209.09598 [math.CO], September 20 2022.
  • Aseem Baranwal, James Currie, Lucas Mol, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, Antisquares and critical exponents, arxiv preprint arXiv:2209.09223 [math.CO], September 19 2022.
  • Luke Schaeffer and Jeffrey Shallit, The first-order theory of binary overlap-free words is decidable, arxiv preprint arXiv:2209.03266 [cs.FL], September 7 2022. Walnut code for the paper:
    • normalize.txt, put in the Automata Library of Walnut
    • CODE.txt, put in the Word Automata Library of Walnut
    • list of all the Walnut commands from the paper
  • Narad Rampersad and Jeffrey Shallit, Congruence properties of combinatorial sequences via Walnut and the Rowland-Yassawi-Zeilberger automaton, Elect. J. Combinatorics 29 (3) (2022), P3.36.
  • Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, and Jeffrey Shallit, Decidability for Sturmian words, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Editors: Florin Manea and Alex Simpson; Article No. 24; pp. 24:1–24:23. Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany. Available here.
  • Jeffrey Shallit, Sonja Linghui Shan, and Kai Hsiang Yang, Automatic sequences in negative bases and proofs of some conjectures of Shevelev, arxiv preprint arXiv:2208.06025 [cs.FL], August 11 2022, available at https://arxiv.org/abs/2208.06025.
  • Jason P. Bell and Jeffrey Shallit, Lie complexity of words, Theoret. Comput. Sci. 927 (2022), 98-108.
  • Trevor Clokie, Thomas F. Lidbetter, Antonio Molina Lovett, Jeffrey Shallit, and Leon Witzman, Computational aspects of sturdy and flimsy numbers, Theoret. Comput. Sci. 927 (2022), 65-86.
  • Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic words and a question of Shevelev, Arxiv preprint, July 21 2022, http://arxiv.org/abs/2207.10171 .
  • Jeffrey Shallit, Using automata and a decision procedure to prove results in pattern matching, in H. Bannai and J. Holub, eds., 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), Article No. 2; pp. 2:1–2:3, Leibniz International Proceedings in Informatics. Available here. (This is just a brief summary of my paper with Schaeffer on string attractors, below.)
  • James Currie, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, Properties of a ternary infinite word. Arxiv preprint arXiv:2206.01776 [cs.DM], June 3 2022. Available at https://arxiv.org/abs/2206.01776. To reproduce the calculations, first download the latest version of Walnut here. Second, put the two files
    • msd_pisot4_addition.txt
    • msd_pisot4.txt
    in the Custom Bases directory. Third, put the file
    • PI.txt
    in the Word Automata directory. Fourth, put the files
    • pisi.txt
    • psynch0.txt
    • psynch1.txt
    • psynch2.txt
    in the Automata Library directory. Finally, all the commands from the paper are in the file
    • pis4.txt

  • Ali Keramatipour and Jeffrey Shallit, Record-setters in the Stern sequence, Arxiv preprint arXiv:2205.06223 [math.CO], May 12 2022. Available at https://arxiv.org/abs/2205.06223.
  • Gabriele Fici and Jeffrey Shallit, Properties of a class of Toeplitz words, Theoret. Comput. Sci. 922 (2022) 1-12. Available at https://doi.org/10.1016/j.tcs.2022.04.006.
  • J. Shallit, Note on a Fibonacci parity sequence, arxiv preprint arXiv:2203.10504 [cs.FL], March 20 2022. Available at https://arxiv.org/abs/2203.10504.
  • J. Shallit, Intertwining of complementary Thue-Morse factors, arxiv preprint arXiv:2203.02917 [cs.FL], March 6 2022. Available at https://arxiv.org/abs/2203.02917. Revised, published version in Australasian J. Combinatorics 84 (2022), 419-430. Available here.
  • J. Shallit, Sumsets of Wythoff sequences, Fibonacci representation, and beyond, Periodica Mathematica Hungarica 84 (2022), 37--46. Available here.
  • J.-P. Allouche, J. Shallit, and R. Yassawi, How to prove that a sequence is not automatic, Expositiones Math. 40 (1) (2022), 1-22.
  • James Haoyu Bai, Joseph Meleshko, Samin Riasat, Jeffrey Shallit, Quotients of palindromic and antipalindromic numbers, arxiv preprint arXiv:2202.13694 [math.NT], Feb 28 2022. Available here. Final revised version in INTEGERS 22 (2022), paper #A96; available here.
  • D. Krenn and J. Shallit, Decidability and k-regular sequences, Theoretical Computer Science 907 (2022), 34-44. Free e-print here.
  • Jason Bell and Jeffrey Shallit, Automatic sequences of rank two, RAIRO-Theor. Inf. Appl. 56 (2022) 7. Available at https://doi.org/10.1051/ita/2022006.
  • Phakhinkon Napp Phunphayap, Prapanpong Pongsriiam, and Jeffrey Shallit, Sumsets associated with Beatty sequences, Discrete Mathematics 345 (2022), 112810.

• 2021
  • Daniel Gabric, Štěpán Holub, and Jeffrey Shallit, Maximal state complexity and generalized de Bruijn words, Info. Comp. 284 (2021), 104689.
    After this paper appeared we became aware of other relevant references, some old and some new. Here they are:
    1. Our generalized de Bruijn words for k=2 appeared in Golomb's book Shift-Register Sequences in Chapter VII, Section 6.
    2. In Blum, Blum, Shub, Comparison of two pseudo-random number generators, in CRYPTO'82, p. 65, the authors define a generalized de Bruijn sequence for base b, which is essentially the same definition we used.
    3. This also appeared in the journal version, of the Blum, Blum, Shub paper, entitled A simple unpredictable pseudo-random number generator, SIAM J. Comput. 15 (1986), 364-383. See p. 370.
    4. For general k they appeared in Max Landsberg's 2000 paper, Feedback functions for generating cycles over a finite alphabet.
    5. And in Hemmati and Costello's 1978 paper An algebraic construction for q-ary shift register sequences.
    6. In Lemma 2 of the paper of Gabrys and Milenkovic, Unique reconstruction of coded strings from multiset substring spectra, IEEE Trans. Info. Theory 65 (2019), 7682-7696, the authors obtain bounds on the number of strings of length n containing no repeated strings of length L.
    7. The paper of Elishco, Gabrys, Yaakobi, and Médard, Repeat-free codes, from ISIT 2019, also contains relevant results. See Theorem 8.
    8. There is also a very new preprint by Nellore and Ward, Arbitrary-length analogs to de Bruijn sequences on the arxiv. It addresses algorithmic concerns. It has appeared in CPM 2022.
    9. There is a new preprint B. Cameron, A. Gündogan, and J. Sawada, Cut-down de Bruijn sequences. It is also mentioned here.
  • L. Fleischer and J. Shallit, Recognizing lexicographically smallest words and computing successors in regular languages, Int. J. Found. Comput. Sci. 32 (6) (2021), 641-662.
  • L. Fleischer and J. Shallit, Automata, palindromes, and reversed subwords, J. Automata Languages Combinatorics 26 (3-4) (2021), 221-253.
  • J. Shallit, Additive Number Theory via Automata and Logic, arxiv preprint arXiv:2112.13627 [math.NT], December 27 2021.
  • G. Fici and J. Shallit, Properties of a Class of Toeplitz Words, arxiv preprint arXiv:2112.12125 [cs.FL], December 23 2021.
    • TP.txt file, place this in the Word Automata directory of Walnut
  • C. S. Kaplan and J. Shallit, A frameless 2-coloring of the plane lattice, Math. Magazine 94 (5) (2021), 353-360. A limited number of free-eprints are available here.
    • Jean-Paul Allouche points out that the result is already known. It appeared in a paper of Hao Wang, Games, logic and computers, Scientific American 213 (5) (November 1965), 98-107.
    • We should have also cited the paper of Salon, Suites automatiques à multi-indices, Sem. Theor. Nombres Bordeaux 4 (1986-7), 4.01-4.27, which proved our Theorem 4 on page 4-21.
  • H. Gruber, J. Lee, and J. Shallit, Enumerating regular expressions and their languages, Chapter 13 of J.-E. Pin, editor, Handbook of Automata Theory, Volume I: Theoretical Foundations, EMS Press, 2021, pp. 459-491.
  • J. Currie, L. Mol, N. Rampersad, and J. Shallit, Extending Dekking's construction of an infinite binary word avoiding abelian 4-powers, Arxiv preprint arXiv:2111.07857 [math.CO], November 15 2021.
  • N. Rampersad and J. Shallit, Congruence properties of combinatorial sequences via Walnut and the Rowland-Yassawi-Zeilberger automaton, Arxiv preprint arXiv:2110.06244 [math.CO], October 12 2021.
  • J. Shallit, Synchronized sequences, in T. Lecroq and S. Puzynina, eds., WORDS 2021, LNICS 12847, Springer, 2021, pp. 1-19.
  • Daniel Gabric, Narad Rampersad, and Jeffrey Shallit, An inequality for the number of periods in a word, Int. J. Found. Comput. Sci. 32 (2021), 597-614.
  • Jason Bell and Jeffrey Shallit, Automatic sequences of rank two, Arxiv preprint arXiv:2108.05434 [cs.FL], August 11 2021.
  • Robert Cummings, Jeffrey Shallit, Paul Staadecker, Mesosome avoidance, Arxiv preprint arXiv:2107.13813 [cs.DM], July 29 2021.
  • J.-P. Allouche, G.-N. Han, and J. Shallit, On some conjectures of P. Barry, J. Number Theory 228 (2021), 108-132.
  • J. Shallit, Hilbert's spacefilling curve described by automatic, regular, and synchronized sequences, Arxiv preprint arXiv:2106.01062 [cs.FL], June 2 2021. Files for the Walnut proofs:
    • HC.txt, put it in the Word Automata directory
    • Walnut commands for section 3
    • HS.txt, put it in the Word Automata directory
    • Walnut commands for section 5
    • Walnut commands for section 6
  • J.-P. Allouche, J. Shallit, and R. Yassawi, How to prove that a sequence is not automatic, Arxiv preprint arXiv:2104.13072 [math.NT], April 27 2021.
  • Daniel Gabric and Jeffrey Shallit, The simplest binary word with only three squares, RAIRO-Theor. Inf. Appl. 55 (2021) 3. Data for the paper:
    • 3squares-proofs.txt
    • Q.txt
    • T1.txt
    • VTM.txt
    • GAB.txt
    • HN.txt
  • Jeffrey Shallit, Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture, Indag. Math. 32 (2021), 729-735.
  • Jeffrey Shallit, Abelian complexity and synchronization, INTEGERS 21 (2021), #A36.
    Here are the files associated with the paper:
    • rst.txt (put this in the "Automata Library" directory of Walnut)
    • TRL.txt (put this in the "Word Automata Library")
    • Walnut commands for the paper
    • TRAC.txt (Walnut DFAO for abelian complexity of Tribonacci word; put in the "Word Automata Library" directory in order to use it)
    • TRAS.txt (Walnut DFAO for subsets of abelian factors of Tribonacci word; put in the "Word Automata Library" directory in order to use it)
  • Jeffrey Shallit, Frobenius numbers and automatic sequences, Arxiv preprint arXiv:2103.10904 [math.NT], March 19 2021. Paper appeared in INTEGERS 21 (2021), #A124 and is available here. Files for the paper:
    • complete Walnut code for all the proofs of the paper
    • shift.txt (put this in the "Automata Library" of Walnut)
    • fibinc.txt (put this in the "Automata Library" of Walnut)
  • Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, Jeffrey Shallit, Decidability for Sturmian words, Arxiv preprint, Feb 16 2021, arXiv:2102.08207 [cs.LO]. Available here.
  • Jason P. Bell and J. Shallit, Lie complexity of words, Arxiv preprint, Feb 7 2021, arXiv:2102.03821 [cs.FL]. Available here.
  • Aseem Baranwal, Luke Schaeffer, and Jeffrey Shallit, Ostrowski-automatic sequences: Theory and applications, Theor. Comput. Sci. 858 (2021) 122-142. Available here until March 11 2021.
  • Jeffrey Shallit, Robbins and Ardila meet Berstel, Info. Proc. Letters 167 (2021). Available at https://doi.org/10.1016/j.ipl.2020.106081. Note: the Robbins-Ardila result was actually proved first by Tad White, On the coefficients of a recursion relation for the Fibonacci partition function, Fib. Quart. 24 (1986), 133-137.

    Corrigendum: There is a typographical error in the definition of the even1 command of Walnut in the paper. It should read

    reg even1 {0,1} "0*(10*10*)*":

    Here are the Walnut commands for the paper:
    rab-computations.txt

  • Daniel Gabric, Jeffrey Shallit, Xiao Feng Zhong, Avoidance of split overlaps, Discrete Mathematics 344 (2021), 112176. Doi: https://doi.org/10.1016/j.disc.2020.112176
  • Daniel Gabric and Jeffrey Shallit, Borders, palindrome prefixes, and square prefixes, Information Processing Letters, 165 (2021), 106027. Doi: https://doi.org/10.1016/j.ipl.2020.106027
  • Luke Schaeffer and Jeffrey Shallit, String attractors for automatic sequences, Arxiv preprint 2012.06840 [cs.FL], January 7 2021. Available at https://arxiv.org/abs/2012.06840. This is a revision of the 2020 version of the paper, adding Luke Schaeffer as co-author. Note added May 29 2024: The proof of part of Theorem 18 has a gap which we currently do not know how to fix. The error is our implicit assumption that (*) if a sequence is automatic and recurrent, then it is uniformly (and hence linearly) recurrent. However, (*) is not true in general (and a counterexample is the Cantor sequence). As a consequence of this oversight, the first two claims of Theorem 18 are currently not proved.

• 2020
  • Jeffrey Shallit, String attractors for automatic sequences, Arxiv preprint 2012.06840v1 [cs.FL], December 12 2020. Available at https://arxiv.org/abs/2012.06840v1.
  • Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences are also non-uniformly morphic, in A. M. Raigorodskii and M. Th. Rassias, eds., Discrete Mathematics and Applications, Springer Optimization and Its Applications, 2020, Vol. 165, pp. 1-6. Available at https://doi.org/10.1007/978-3-030-55857-4_1.
  • Jason Bell, Thomas F. Lidbetter, and Jeffrey Shallit, Additive number theory via approximation by regular languages, International Journal of Foundations of Computer Science 31 (6) (2020) 667-687. Available here.
  • Jeffrey Shallit, Length of the continued logarithm algorithm on rational inputs, INTEGERS 20 (2020), Paper A69. Available here.
  • Jeffrey Shallit, Abelian complexity and synchronization, arxiv preprint, November 1 2020.
    Here are the files associated with the paper:
    • rst.txt (put this in the Result directory of Walnut)
    • TRL.txt (put this in the Word Automata Library)
    • Walnut commands for the paper
    • TRAC.txt (Walnut DFAO for abelian complexity of Tribonacci word; put in the Word Automata Library directory in order to use it)
    • TRAS.txt (Walnut DFAO for subsets of abelian factors of Tribonacci word; put in the Word Automata Library directory in order to use it)
  • Jeffrey Shallit, Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture, arxiv preprint arXiv:2010.10956 [cs.DM], October 21 2020. Submitted.
    Files for the paper:
    • FTM.txt, put this in the "Word Automata" library of Walnut
    • FTMD.txt, put this in the "Word Automata" library of Walnut
    • walnut commands
    • ftmatrix.mpl, the Maple code for the matrix

  • Aaron Potechin and Jeffrey Shallit, Lengths of words accepted by nondeterministic finite automata, Info. Proc. Letters 162 (2020), 105993. doi: https://doi.org/10.1016/j.ipl.2020.105993.
  • Lukas Fleischer, Samin Riasat, and Jeffrey Shallit, New bounds on antipowers in words, Information Processing Letters 164 (2020). Doi: https://doi.org/10.1016/j.ipl.2020.106021
  • Carlo Sanna, Jeffrey Shallit, Shun Zhang, The Largest Entry in the Inverse of a Vandermonde Matrix, Arxiv preprint 2008.01012, August 3 2020.
  • Jeffrey Shallit, Robbins and Ardila meet Berstel, Arxiv preprint 2007.14930, July 29 2020.
    • Walnut commands for the paper
  • Daniel Gabric and Jeffrey Shallit, The simplest binary word with only three squares, Arxiv preprint 2007.08188, July 17 2020. Data for the paper:
    • 3squares-proofs.txt
    • Q.txt
    • T1.txt
    • VTM.txt
    • GAB.txt
    • HN.txt
  • Dmitry Badziahin and Jeffrey Shallit, Badly approximable numbers, Kronecker's theorem, and diversity of Sturmian characteristic sequences, Arxiv preprint 2006.15842, June 29 2020. Submitted.
  • Lucas Mol, Narad Rampersad, and Jeffrey Shallit, Extremal overlap-free and extremal β-free binary words, Arxiv preprint 2006.10152, June 17 2020. Appeared in Electronic J. Combinatorics, 27 (4) (2020), P4.42.
  • J.-P. Allouche, G.-N. Han, and J. Shallit, On some conjectures of P. Barry, Arxiv preprint 2006.08909, June 16 2020.
  • Jeffrey Shallit, Sumsets of Wythoff sequences, Fibonacci representation, and beyond, arxiv preprint 2006:04177, June 7 2020. Appeared in 2021 (above).
  • Lukas Fleischer and Jeffrey Shallit, The State Complexity of Lexicographically Smallest Words and Computing Successors, in N. Jonoska and D. Savchuk, eds., DLT 2020, LNCS 12086, pp. 83-95, 2020.
  • Jean-Paul Allouche, Jeffrey Shallit, Zhi-Xiong Wen, Wen Wu, and Jie-Meng Zhang, Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences, Discrete Math. 343 (2020), Paper 111958.
  • Daniel Gabric, Narad Rampersad, and Jeffrey Shallit, An inequality for the number of periods in a word, arxiv preprint, May 25 2020.
    • Walnut code for Theorems 15 and 16
  • Aseem Baranwal, Luke Schaeffer, and Jeffrey Shallit, Ostrowski-Automatic Sequences: Theory and Applications, submitted, May 24 2020. This is the journal version of our two conference papers that appeared in WORDS 2019.
  • Craig S. Kaplan and Jeffrey Shallit, A Frameless 2-Coloring of the Plane Lattice, Arxiv preprint, May 19 2020. Submitted.
  • Daniel Krenn and Jeffrey Shallit, Decidability and k-Regular Sequences, Arxiv preprint, May 19 2020. Submitted.
  • Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith, Additive Number Theory via Automata Theory, Theor. Comput. Sys. 64 (2020) 542-567.
  • F. Michel Dekking, Jeffrey Shallit, N. J. A. Sloane, Queens in exile: non-attacking queens on infinite chess boards, Elect. J. Combinatorics, 27 (1) (2020), P1.52.
  • P. Gawrychowski, M. Lange, N. Rampersad, J. Shallit, M. Szykula, Existential Length Universality, in Christophe Paul and Markus Bläser, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), LIPICS Vol. 154, 16.1-16.14.
  • Trevor Clokie, Thomas F. Lidbetter, Antonio Molina Lovett, Jeffrey Shallit, Leon Witzman, Computational Aspects of Sturdy and Flimsy Numbers, arxiv preprint, February 7 2020. To appear, proceedings of FUN 2020 conference. That version is available here.
  • Daniel Gabric and Jeffrey Shallit, Avoidance of split overlaps, arxiv preprint, February 5 2020. Submitted.
  • Paul C. Bell, Daniel Reidenbach, Jeffrey O. Shallit, Unique decipherability in formal languages, Theoretical Computer Science 804 (2020) 149-160.

• 2019
  • Therese C. Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey O. Shallit, Rollercoasters: long sequences without short runs. SIAM J. Discret. Math. 33 (2) (2019) 845-861.
  • Jeffrey O. Shallit and Arseny M. Shur, Subword complexity and power avoidance, Theor. Comput. Sci. 792 (2019), 96-116.
  • Daniel M. Kane, Carlo Sanna, and Jeffrey Shallit, Waring's theorem for binary powers, Combinatorica 39 (2019), 1335-1350.
  • Lucas Mol, Narad Rampersad, Jeffrey Shallit, and Manon Stipulanti, Cobham's theorem and automaticity, International Journal of Foundations of Computer Science 30 (8) (2019), 1363-1379.
    Corrigendum: Corollary 5 (p. 1376) gives a lower bound on the b-automaticity of an aperiodic a-automatic sequence for multiplicatively independent a,b. In the discussion following Corollary 5 and again in the "Final Thoughts" on p. 1378, we compared this bound with some results from one of my papers, "Automaticity IV: sequences, sets, and diversity". However, the comparison is not valid, because that older paper used lsd-first representation, whereas the 2019 paper uses msd-first.
  • Lukas Fleischer, Samin Riasat, Jeffrey Shallit, New Bounds on Antipowers in Binary Words, arxiv preprint, December 17 2019.
  • Lukas Fleischer, Jeffrey Shallit, Words with few palindromes, revisited, arxiv preprint, November 27 2019.
    • tar file with all programs for the paper
  • Lukas Fleischer, Jeffrey Shallit, Words Avoiding Reversed Factors, Revisited, arxiv preprint, November 26 2019.
    • tar file with all programs for the paper
  • I. P. Goulden, Andrew Granville, L. Bruce Richmond, Jeffrey Shallit, Natural exact covering systems and the reversion of the Möbius series, Ramanujan J. 50 (2019), 211-235.
  • Antonio Molina Lovett and Jeffrey Shallit, Optimal Regular Expressions for Permutations, in Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, eds., 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2019, pp. 121:1-12. Available at http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=10697.
  • F. Michel Dekking, Jeffrey Shallit, N. J. A. Sloane, Queens in exile: non-attacking queens on infinite chess boards, arxiv preprint, July 22 2019. Submitted.
  • Narad Rampersad, Jeffrey Shallit, Élise Vandomme, Critical exponents of infinite balanced words, Theoret. Comput. Sci. 777 (2019), 454-463. Available here.
  • Daniel Gabric, Jeffrey Shallit, Borders, palindrome prefixes, and square prefixes, arxiv preprint, June 9 2019. Submitted.
  • Aseem Raj Baranwal, Jeffrey Shallit, Repetitions in infinite palindrome-rich words, arxiv preprint, April 22 2019. In R. Mercas and D. Reidenbach, eds., Combinatorics on Words. WORDS 2019. Lecture Notes in Computer Science, vol. 11682, Springer, 2019, pp. 93-105. Available here.
  • Jean-Paul Allouche, Samin Riasat, Jeffrey Shallit: More Infinite Products: Thue-Morse and the Gamma function, Ramanujan J. 49 (2019), 115-128.
  • Tim Ng, Pascal Ochem, Narad Rampersad, Jeffrey Shallit, New results on pseudosquare avoidance, arxiv preprint, April 19 2019. Conference version in R. Mercas and D. Reidenbach, eds., Combinatorics on Words. WORDS 2019. Lecture Notes in Computer Science, vol. 11682, Springer, 2019, pp. 264-274. Available here.
  • T. Clokie, D. Gabric, and J. Shallit, Circularly squarefree words and unbordered conjugates: a new approach, arxiv preprint, April 17 2019. In R. Mercas and D. Reidenbach, eds., Combinatorics on Words. WORDS 2019. Lecture Notes in Computer Science, vol. 11682, Springer, 2019, pp. 133-144. Available here.
    Walnut code to check the claims in the paper:
    • cyclically-squarefree.txt
    • unbordered-factors.txt
  • D. Gabric, S. Holub, and J. Shallit, Generalized de Bruijn words and the state complexity of conjugate sets, arxiv preprint, March 13 2019. Appeared in M. Hospodár et al. (Eds.): DCFS 2019, Springer, LNCS 11612, pp. 137–146, 2019.

    Theorem 8 (Theorem 3 in the conference version) in the first version of the paper above is incorrect, and the proposed proof is not correct. However, it can be easily fixed by replacing the requirement that N ≥ 2r+1 with N ≥ 3r+1 and a different proof. Hence everything else (in particular Corollary 9 (or Corollary 1 in the conference version)) in the paper remains proved.

    The new arxiv version of the paper fixes this error.

  • Sajed Haque and Jeffrey Shallit, A class of exponential sequences with shift-invariant discriminators, Fibonacci Quart. 57 (2019) 1-9.
  • Lukas Spiegelhofer and Jeffrey Shallit, Continuants, Run Lengths, and Barry's Modified Pascal Triangle, Electron. J. Combinatorics 26 (1) (2019), paper P1.31.
  • Aseem R. Baranwal, Jeffrey Shallit, Critical exponent of infinite balanced words via the Pell number system, arxiv Preprint, February 1 2019. In R. Mercas and D. Reidenbach, eds., Combinatorics on Words. WORDS 2019. Lecture Notes in Computer Science, vol. 11682, Springer, 2019, pp. 80-92. Available here.
  • Jeffrey Shallit and Ramin Zarifi, Circular critical exponents for Thue–Morse factors, RAIRO Info. Theor. 53 (2019) 37-49. Available here.
  • Pierre Bonardo, Anna E. Frid, Jeffrey Shallit, The number of valid factorizations of Fibonacci prefixes, Theor. Comput. Sci. 775 (2019) 68-75. Available online at https://doi.org/10.1016/j.tcs.2018.12.016.

• 2018
  • J.-P. Allouche and J. Shallit, Michel Mendès France (1936--2018), obituary, in La Gazette des Mathématiciens of the Soc. Math. de France, No. 158, October 2018, pp. 81-83.
  • Jason Bell, Kathryn Hare and Jeffrey Shallit, When is an automatic set an additive basis? Proc. Amer. Math. Soc. Ser. B 5 (2018), 50-63. Available here.
  • Pierre Bonardo, Anna E. Frid, Jeffrey Shallit, Number of valid decompositions of Fibonacci prefixes, arxiv preprint, June 25 2018. To appear, Theoretical Computer Science.
  • Lucas Mol, Narad Rampersad, Jeffrey Shallit, and Manon Stipulanti, Cobham's theorem and automaticity, arxiv preprint 1809.00679, December 2018.
  • Antonio Molina Lovett and Jeffrey Shallit, Optimal regular expressions for permutations, arxiv preprint 1812.06347, 15 Dec 2018.
  • P. Madhusudan, Dirk Nowotka, Aayush Rajasekaran, and Jeffrey Shallit, Lagrange's theorem for binary squares, winner of the best paper award at 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Igor Potapov, Paul Spirakis, and James Worrell, eds., Article No. 18, pp. 18:1–18:14, Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany.
  • Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit, Rollercoasters and caterpillars, ICALP 2018, LIPICS conference proceedings, 18:1-18:15.
  • Jeffrey Shallit and Ramin Zarifi, Circular critical exponents for Thue-Morse factors, arxiv preprint, August 7 2018.
    • Walnut commands for the Thue-Morse sequence results
    • Walnut commands for the paperfolding sequence
  • Charles J. Colbourn, Ryan E. Dougherty, Thomas F. Lidbetter, and Jeffrey Shallit, Counting subwords and regular languages, arxiv preprint, April 30 2018. Appeared in M. Hoshi and S. Seki, eds., DLT 2018, LNCS Vol. 11088, Springer, 2018, pp. 231-242.
  • Jason Bell, Thomas Finn Lidbetter, and Jeffrey Shallit, Additive Number Theory via Approximation by Regular Languages, arxiv preprint, April 23 2018. Appeared in M. Hoshi and S. Seki, eds., DLT 2018, LNCS Vol. 11088, Springer, 2018, pp. 121-132. Here are text files describing how you can verify the results yourself using Grail and Walnut.
    • Theorem 2
    • Theorem 5
    • Theorem 7
    • Theorem 9
    • Theorem 12
    • Theorem 15
  • Jean-Paul Allouche, Samin Riasat, Jeffrey Shallit: More Infinite Products: Thue-Morse and the Gamma function, Ramanujan J., published online, February 23 2018. Can be viewed via this link.
  • Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith, Sums of palindromes: an approach via automata, in Rolf Niedermeier and Brigitte Vallée, eds., 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Article No. 54; pp. 54:1–54:12. The source files for the claims in this paper can be found at https://github.com/arajasek/FinalGenerators.
  • Aaron Potechin and Jeffrey Shallit, Lengths of Words Accepted by Nondeterministic Finite Automata, arxiv preprint, February 13 2018.
  • Andrew Bridy, Robert J. Lemke Oliver, Arlo Shallit, and Jeffrey Shallit, The Generalized Nagell-Ljunggren Problem: Powers with Repetitive Representations, Experimental Math. 28 (2019), 428-439. Free e-print here. There is a typo on page 5 (left), where in the very last line on the left side, the equation should read z = t⁴/p²... in place of z = t²/p... In this paper we should have referred to R. Ondrejka, Problem 1130: biperiod squares, J. Recreational Math. 14 (1981-2) 299. Solution by F. H. Kierstead, Jr., J. Recreational Math. 15 (1982-3), 311-312.
  • Narad Rampersad and Jeffrey Shallit, Common factors in automatic and Sturmian sequences, arxiv preprint, February 11 2018.
  • Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, Jeffrey Shallit, Rollercoasters and Caterpillars, arxiv preprint, January 25 2018. To appear, ICALP 2018.
  • Narad Rampersad, Jeffrey Shallit, Élise Vandomme, Critical exponents of infinite balanced words, arxiv preprint, January 16 2018.
  • Jeffrey Shallit and Arseny M. Shur, Subword complexity and power avoidance, arxiv preprint, January 16 2018.
  • Daniel M. Kane, Carlo Sanna, and Jeffrey Shallit, Waring's theorem for binary powers, arxiv preprint, January 13 2018.

• 2017
  • A. Rajasekaran, N. Rampersad, J. Shallit, Overpals, Underlaps, and Underpals, in WORDS 2017: Combinatorics on Words, 2017, pp. 17-29.
  • J.-P. Allouche, J. Cassaigne, J. Shallit, and L. Q. Zamboni, A taxonomy of morphic sequences, arxiv preprint, November 29 2017.
  • I. P. Goulden, L. Bruce Richmond, and Jeffrey Shallit, "Natural exact covering systems and the reversion of the Möbius series", arxiv preprint, December 12 2017. The APL code (runs on Dyalog APL) is as follows (the main function is K CDCSM N):
    • part 1
    • part 2
    There is also
    • Maple code to compute some of the constants in the paper
  • Jason P. Bell, Kathryn E. Hare, and Jeffrey Shallit, "When is an automatic set an additive basis?", arxiv preprint, October 23 2017. Submitted. The following file explains how to get Walnut prove the examples in Section 6 of the paper.
    • examples
  • Jeffrey Shallit and Lukas Spiegelhofer, "Continuants, run lengths, and Barry's modified Pascal triangle", arxiv preprint, October 17 2017. Submitted.
  • Parthasarathy Madhusudan, Dirk Nowotka, Aayush Rajasekaran, Jeffrey Shallit, "Lagrange's Theorem for Binary Squares", arxiv preprint, October 11 2017. The machine proofs for the paper are here in a zip file.
  • Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith, "Sums of palindromes: an approach via automata", submitted to STACS, September 2017. The source code referred to in this paper is as follows:
    For Theorem 1:
    PalConjecture.ats
    OddPalindromes1.cpp
    OddPalindromes4.cpp

    For Theorem 5:
    PalBase3Conjecture.ats
    PalBase3NFAUnioned.cpp
    PalBase3ConjectureTest1.ats

    For Theorem 6:
    PalBase4Conjecture.ats
    PalindromesBase4.cpp

    and can be found at https://github.com/arajasek/PalGenerators, or downloaded here.

  • Jean-Paul Allouche, Samin Riasat, Jeffrey Shallit: More infinite products: Thue-Morse and the Gamma function, arxiv preprint, September 11 2017. Submitted.
  • Gabriele Fici, Filippo Mignosi, Jeffrey Shallit: Abelian-square-rich words. Theor. Comput. Sci. 684 (2017), 29-42.
  • Yu Hin (Gary) Au, Christopher Drexler-Lemire, and Jeffrey Shallit, "Notes and note pairs in Norgard's infinity series", J. of Mathematics and Music 11 (1) (2017) 1-19. DOI: here.
  • Andrew Bridy, Robert J. Lemke Oliver, Arlo Shallit, and Jeffrey Shallit, "The Generalized Nagell-Ljunggren Problem: Powers with Repetitive Representations", arxiv preprint, July 14 2017. Submitted.
  • Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith, "Sums of palindromes: an approach via nested-word automata", preprint July 2 2017. Here is the ULTIMATE automata library code that accompanies the paper:
    • Code proving Theorem 1
    • Code proving Proposition 5
    • Code proving Theorem 6
    • Code proving Theorem 11a
    • Code proving Theorem 11b
    • Code proving Theorem 18
  • Robbert Fokkink, Cor Kraaikamp, and Jeffrey Shallit, Hankel matrices for the period-doubling sequence, Indag. Math. 28 (2017), 108-119.
  • Jörg Endrullis, Jeffrey Shallit, and Tim Smith, Undecidability and finite automata, preprint, February 5 2017. Final version in E. Charlier et al., eds., Proc. DLT 2017, Springer Lecture Notes in Computer Science, Vol. 10396 (2017), pp. 160-172.
  • Sajed Haque and Jeffrey Shallit, A class of exponential sequences with shift-invariant discriminators, preprint, February 2 2017. Accepted for Fibonacci Quarterly.
  • Dmitry Chistikov, Szabolcs Ivan, Anna Lubiw, and Jeffrey Shallit, Fractional coverings, greedy coverings, and rectifier networks, STACS 2017, LIPICS, 2017, 23:1--23:14.
  • Chen Fei Du, Hamoon Mousavi, Eric Rowland, Luke Schaeffer, and Jeffrey Shallit, Decision Algorithms for Fibonacci-Automatic Words, II: Related Sequences and Avoidability, Theoret. Comput. Sci. 657 (2017), 146-162.
  • Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit, and Taylor J. Smith, Periodicity in rectangular arrays, Information Processing Letters 118 (2017) 58-63.

• 2016
  • Curtis Bright, Raymond Devillers, and Jeffrey Shallit, Minimal elements for the prime numbers, Experimental Mathematics 25 (3) (2016), 321-331.
  • Minimum critical exponents for palindromes, preprint, December 16 2016.
  • Narad Rampersad and Jeffrey Shallit, Repetitions in words, in Combinatorics, Words and Symbolic Dynamics, Cambridge University Press, Encyclopedia of Mathematics and Its Applications 159, 2016, pp. 101-150.
  • Chuan Guo, Jeffrey Shallit, and Arseny M. Shur, Palindromic rich words and run-length encodings, Information Processing Letters 116 (2016), 735-738.
  • Michael Forsyth, Amlesh Jayakumar, Jarkko Peltomäki, and J. Shallit, Remarks on privileged words, Int. J. Found. Comput. Sci., 27 (2016), 431-442. Examples from the paper that can be run with Walnut (download Walnut below):
    • Thue-Morse examples
    • Rudin-Shapiro examples
    • Rudin-Shapiro example for trapezoidal words
    • paperfolding sequence examples
    • paperfolding example for trapezoidal words
    • period-doubling examples
    • Fibonacci examples
    You'll also need to put the following files in the "Word Automata" library:
    • RS.txt (automaton for Rudin-Shapiro)
    • P.txt (msd automaton for paperfolding)
    • PR.txt (lsd automaton for paperfolding)
    • PD.txt (automaton for period-doubling)

  • J. Shallit, Length of the continued logarithm algorithm on rational inputs, preprint, June 13 2016.
  • J.-P. Allouche and J. Shallit, On the subword complexity of the fixed point of a → aab, b → b, and generalizations, preprint, May 8 2016.
  • Sajed Haque and Jeffrey Shallit, Discriminators and k-regular sequences, preprint, April 30 2016. In INTEGERS 16 (2016), Paper #A76. here
  • Luke Schaeffer and Jeffrey Shallit, Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences, Elect. J. Combinatorics 23 (1) (2016), Paper #P1.25.
  • Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, and Jeffrey Shallit, Decision algorithms for Fibonacci-automatic words, III: enumeration and abelian properties, Int. J. Found. Comput. Sci. 27 (8) (2016), 943-963.
  • Štěpán Holub and Jeffrey Shallit, Periods and borders of random words, in Proc. of STACS 2016.
  • Hamoon Mousavi, Luke Schaeffer, and Jeffrey Shallit, Decision algorithms for Fibonacci-automatic words, I: basic results, RAIRO Inform. Théorique 50 (2016), 39-66. E-version: here

• 2015
  • Daniel Goc, Hamoon Mousavi, Luke Schaeffer, Jeffrey Shallit, A new approach to the paperfolding sequences, in Arnold Beckmann, Victor Mitrana, Mariya Soskova, eds., Evolving Computability: 11th Conference on Computability in Europe, CiE 2015, Springer, LNICS, Vol. 9136, 2015, pp. 34-43. Available here.
  • Chen Fei Du, Jeffrey Shallit, and Arseny M. Shur, Optimal bounds for the similarity density of the Thue-Morse word with overlap-free and 7/3-power-free infinite binary words, International Journal of Foundations of Computer Science 26 (8) (2015) 1147-1165.
  • J. Shallit, Enumeration and automatic sequences, Pure Mathematics and Applications 25 (1) (2015), 96-106. Available here.
  • Robbert Fokkink, Cor Kraaikamp, and Jeffrey Shallit, Hankel matrices for the period-doubling sequence, preprint, November 20 2015.
  • Dmitry Chistikov, Szabolcs Iván, Anna Lubiw, and Jeffrey Shallit, Fractional coverings, greedy coverings, and rectifier networks, submitted, September 2015.
  • Štěpán Holub and Jeffrey Shallit, Periods and borders of random words, preprint, September 17 2015.
  • H. Mousavi and J. Shallit, Mechanical proofs of properties of the Tribonacci word, in F. Manea and D. Nowotka, eds., WORDS 2015, LNCS 9304, Springer, 2015, pp. 1-21. Here are the Walnut predicates you can use to reproduce most of the results in this paper:
    • predicates
    • TR.txt, put in the "Word Automata" library
  • Luke Schaeffer and Jeffrey Shallit, Closed, rich, privileged, trapezoidal, and balanced words in automatic sequences, preprint, August 9 2015.
    Examples from the paper that can be run with Walnut (download Walnut below):
    • Thue-Morse examples
    • Rudin-Shapiro examples
    • Rudin-Shapiro example for trapezoidal words
    • paperfolding sequence examples
    • paperfolding example for trapezoidal words
    • period-doubling examples
    • Fibonacci examples
    You'll also need to put the following files in the "Word Automata" library:
    • RS.txt (automaton for Rudin-Shapiro)
    • P.txt (msd automaton for paperfolding)
    • PR.txt (lsd automaton for paperfolding)
    • PD.txt (automaton for period-doubling)

  • Eric Rowland and Jeffrey Shallit, Automatic sets of rational numbers, Int. J. Found. Comput. Sci. 26 (2015), 343-365.
  • Dzmitry Badziahin and Jeffrey Shallit, An unusual continued fraction, May 2015. Appeared in Proc. Amer. Math. Soc. 144 (2016), 1887-1896.
  • Hamoon Mousavi, Luke Schaeffer, and Jeffrey Shallit, Decision algorithms for Fibonacci-automatic words, I: basic results, submitted, April 2015.
  • Chen Fei Du, Hamoon Mousavi, Eric Rowland, Luke Schaeffer, and Jeffrey Shallit, "Decision algorithms for Fibonacci-automatic words, II: related sequences and avoidability", submitted, April 2015.
  • Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, and Jeffrey Shallit, Decision algorithms for Fibonacci-automatic words, III: enumeration and Abelian properties, submitted, April 2015.
    • Walnut Prover, written by Hamoon Mousavi, and used in the papers above. If you use it, please cite Hamoon Mousavi as the author.
    • Some examples of how to use Walnut
    • The Walnut Manual by Hamoon Mousavi (new: March 2 2016)
  • Chuan Guo, Jeffrey Shallit, Arseny Shur, On the combinatorics of palindromes and antipalindromes, submitted, March 2015.
  • Paul Bell, Daniel Reidenbach, Jeffrey Shallit, Factorization in formal languages, preprint, March 2015. Appeared in I. Potapov, ed., DLT 2015, LNCS 9168, Springer, 2015, pp. 97-107.
  • Kevin Ford, Florian Luca, Carl Pomerance, and Jeffrey Shallit, On the parity of the number of small divisors of n, in C. Pomerance and M. Th. Rassias, eds., Analytic Number Theory, Springer, 2015, pp. 93-100.
  • C. Bright, R. Devillers, and J. Shallit, Minimal elements for the prime numbers, submitted, January 2015.

• 2014
  • Julien Cassaigne, James D. Currie, Luke Schaeffer, Jeffrey Shallit, Avoiding three consecutive blocks of the same size and same sum. J. ACM 61 (2) (2014), Paper 10.
  • H. Mousavi and J. Shallit, Mechanical proofs of properties of the Tribonacci word, preprint, July 2014.
  • L. Bruce Richmond and J. Shallit, Counting the palstars, revised preprint at http://arxiv.org/abs/1311.2318, June 2014. Appeared in Electronic J. Combinatorics 21 (3) (2014), Paper #P3.25. Corrigendum: in Section 4, P_k should be p_k.
  • Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, and Jeffrey Shallit, Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance, preprint, June 3 2014.
  • Eric Rowland and Jeffrey Shallit, Automatic sets of rational numbers. Revised and expanded version of our LATA 2012 paper, February 2014. To appear, Int. J. Found. Comput. Sci..
  • Christopher Drexler-Lemire and Jeffrey Shallit, Notes and note-pairs in Noergaards's infinity series, preprint, February 2014. Submitted.
  • Kevin Hare, Helmut Prodinger, and Jeffrey Shallit, Three series for the generalized golden mean, preprint, January 2014. Appeared in Fibonacci Quarterly 52 (4) (2014), 307-313.

• 2013
  • Michael Forsyth, Amlesh Jayakumar, Jeffrey Shallit, Remarks on privileged words, submitted.
  • Emilie Charlier, Michael Domaratzki, Tero Harju, and Jeffrey Shallit, Composition and orbits of language operations: finiteness and upper bounds, Int. J. Comput. Math. 90 (6) (2013), 1171-1196.
  • J. Shallit, Counting palstars, preprint at http://arxiv.org/abs/1311.2318, November 2013.
  • J. Shallit, Description of generalized continued fractions by finite automata, in J. M. Borwein, I. Shparlinski, and W. Zudilin, eds., Number Theory and Related Fields: In Memory of Alf van der Poorten, Springer-Verlag, 2013, pp. 321-339.
  • S. Tan and J. Shallit, Sets represented as the length-n factors of a word, preprint at http://arxiv.org/abs/1304.3666. In Juhani Karhumäki, Arto Lepistö, and Luca Zamboni, eds., Combinatorics on Words: 9th International Conference, WORDS 2013, Turku, Finland, September 16-20, Proceedings, Lecture Notes in Computer Science, Vol. 8079, Springer, 2013, pp. 250-261. Published version available here.
  • H. Mousavi and J. Shallit, Shortest repetition-free words accepted by automata, preprint at http://arxiv.org/abs/1304.2959. In Helmut Jurgensen and Rogerio Reis, Descriptional Complexity of Formal Systems: 15th International Workshop, DCFS 2013, London, Canada, July 22-25, 2013, Proceedings, Lecture Notes in Computer Science, Vol. 8031, Springer, 2013, pp. 182-193. Published version available here.
  • J. Shallit, Decidability and enumeration for automatic sequences: a survey, in A. A. Bulatov and A. M. Shur, eds., CSR 2013, LNCS 7913, Springer, 2013, pp. 49-63.
  • D. Goc, K. Saari, and J. Shallit, Primitive words and Lyndon words in automatic and linearly recurrent sequences, in A.-H. Dediu, C. Martin-Vide, and B. Truthe, eds., LATA 2013, LNCS 7810, 2013, pp. 311-322.
  • Daniel Goc, Hamoon Mousavi, and Jeffrey Shallit, On the number of unbordered factors, in A.-H. Dediu, C. Martin-Vide, and B. Truthe, eds., LATA 2013, LNCS 7810, 2013, pp. 299-310. Available here.
  • Hamoon Mousavi and Jeffrey Shallit, Filtrations of formal languages by arithmetic progressions, Fundam. Inform. 123 (2) (2013), 135--142.
  • Daniel Goc, Dane Henshall, and Jeffrey Shallit, Automatic theorem-proving in combinatorics on words, Int. J. Found. Comput. Sci. 24 (6) (2013), 781-798.
    Corrigendum: the last few lines of page 793 (logical page 13 of the paper) are not correct, and should be replaced by the following:
     

• 2012
  • Jean-Paul Allouche and Jeffrey Shallit, A variant of Hofstadter's sequence and finite automata, J. Aust. Math. Soc. 93 (2012), 1-8. Available here, copyright Cambridge University Press. Corrigenda in published version:
    • In Table 3 on page 6, the second occurrence of 10111 in the table in the column labeled q should actually be 11101.
    • In Table 4 on page 7, the line for 110 is missing. It should read q = 110, δ′(q,0) = 1100, δ′(q,1) = 1101, τ′(q) = 2.
    • Also, in the same Table, the line that reads 110011 in column q should actually be 1110011.
  • Luke Schaeffer and Jeffrey Shallit, The critical exponent is computable for automatic sequences, Int. J. Found. Comput. Sci. 23 (2012), 1611-1626. doi
  • Hamoon Mousavi and Jeffrey Shallit, Repetition avoidance in circular factors, preprint, December 2012. Appeared in Marie-Pierre Béal and Olivier Carton, eds., Developments in Language Theory 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings, Lecture Notes in Computer Science, Volume 7907, Springer, 2013, pp. 384-395. Available here.
  • Daniel Goc, Hamoon Mousavi, and Jeffrey Shallit, "On the number of unbordered factors", preprint, November 2012. Submitted.
  • Alex Leong and J. Shallit, Counting sequences with small discrepancies, Experimental Mathematics, 22 (2013), 74-84. Data and programs for the paper here. The proof for p < 2³²¹⁷ - 1 is given here. By the way, the most recently discovered Mersenne prime is 2^57885161 - 1, which is also covered by the results in our paper, since 57885161 ≡ 41 (mod 96).
  • D. Henshall, N. Rampersad, and J. Shallit, Shuffling and unshuffling, Bull. EATCS, No. 107, June 2012, pp. 131-142. Electronically available here.
  • E. Charlier, N. Rampersad, J. Shallit, Enumeration and decidable properties of automatic sequences, Int. J. Found. Comput. Sci., 23 (2012), 1035-1066. DOI
  • Narad Rampersad, Jeffrey Shallit, and Zhi Xu, The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages Fundam. Inform. 116 (1-4) (2012), 223-236.
  • D. Goc and J. Shallit, Least periods of k-automatic sequences, preprint, July 2012.
  • D. Goc, K. Saari, and J. Shallit, Primitive words and Lyndon words in automatic and linearly recurrent sequences, preprint, July 2012. Revised, November 2012. Submitted. In A.-H. Dediu, C. Martin-Vide, and B. Truthe, eds., LATA 2013, LNCS 7810, Springer, 2013, pp. 311-322.
  • D. Goc, L. Schaeffer, and J. Shallit, The subword complexity of k-automatic sequences is k-synchronized, preprint, June 2012. In Marie-Pierre Béal and Olivier Carton, eds., Developments in Language Theory 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings, Lecture Notes in Computer Science, Volume 7907, Springer, 2013, pp. 252-263. Available here.
  • G. Jirásková and J. Shallit, The state complexity of star-complement-star, preprint, March 2012. In H.-C. Yen and O. H. Ibarra, eds., Developments in Language Theory - 16th International Conference, DLT 2012, Lect. Notes in Computer Science, Vol. 7410, Springer, 2012, pp. 380-391. doi
  • D. Goc, D. Henshall, and J. Shallit, Automatic theorem-proving in combinatorics on words, preprint, March 2012. In N. Moreira and R. Reis, CIAA 2012, Lect. Notes in Computer Science, Vol. 7381, Springer, 2012, pp. 180-191. Available here.
  • E. Rowland and J. Shallit, Avoiding 3/2-powers over the natural numbers, Discrete Mathematics 312 (2012), 1282-1288.

• 2011
  • J. Brzozowski and E. Grant and J. Shallit, Closures in formal languages and Kuratowski's theorem, Int. J. Found. Comput. Sci. 22 (2011), 301-321. Corrigendum: Case 2a should have |E(L)|=4, and Case 2b should have |E(L)|=3.
  • Y. Au, A. Robertson and J. Shallit, Van der Waerden’s Theorem and Avoidability in Words, Integers 11 (2011), 61-76.
  • H. Mousavi and J. Shallit, Filtrations of formal languages by arithmetic progressions, preprint, December 2011.
  • E. Rowland and J. Shallit, k-automatic sets of rational numbers, preprint, October 2011. In A.-H. Dediu and C. Martin-Vide, eds., Proc. LATA 2012, LNCS 7183, 2012, pp. 490-501.
  • D. Henshall, N. Rampersad, and J. Shallit, Shuffling and unshuffling, preprint, June 28 2011. Submitted.
  • J. Cassaigne, J. D. Currie, L. Schaeffer, and J. Shallit, Avoiding three consecutive blocks of the same size and same sum, preprint, June 26 2011. Submitted.
  • Y. Bugeaud, D. Krieger, and J. Shallit, Morphic and automatic words: maximal blocks and Diophantine approximation, Acta Arith. 149 (2011), 181-199.
  • M. Coons and J. Shallit, A pattern sequence approach to Stern's sequence, Discrete Math., 311 (2011), 2630-2633.
  • N. Rampersad, J. Shallit, and A. Shur, Fife's theorem for (7/3)-powers. In P. Ambroz, S. Holub, and Z. Masakova, eds., WORDS 2011, 8th International Conference, pp. 189-198.
  • J. F. Morgenbesser, J. Shallit, and T. Stoll, Thue-Morse at multiples of an integer, J. Number Theory 131 (2011), 1498-1512. DOI link
  • J. Shallit, The critical exponent is computable for automatic sequences. In P. Ambroz, S. Holub, and Z. Masakova, eds., WORDS 2011, 8th International Conference, pp. 231-239. Revised version with Luke Schaeffer, submitted.
  • J. Shallit and J. Stankewicz, Unbounded discrepancy in Frobenius numbers, INTEGERS 11 (2011), paper A2.
  • E. D. Demaine, S. Eisenstat, J. Shallit, and D. A. Wilson, Remarks on separating words, in M. Holzer, M. Kutrib, and G. Pighizzini, eds., Descriptional Complexity of Formal Systems, 13th International Workshop, DCFS 2011, Lecture Notes in Comp. Sci., Vol. 6808, Springer, 2011, pp. 147-157.
  • L. Alpoge, T. Ang, L. Schaeffer, and J. Shallit, Decidability and Shortest Strings in Formal Languages, in M. Holzer, M. Kutrib, and G. Pighizzini, eds., Descriptional Complexity of Formal Systems, 13th International Workshop, DCFS 2011, Lecture Notes in Comp. Sci., Vol. 6808, Springer, 2011, pp. 55-67.
  • J.-P. Allouche and J. Shallit, A variant of Hofstadter's sequence and finite automata, preprint. Submitted.
  • J. Shallit, Fife's theorem revisited, in G. Mauri and A. Leporati, eds., Developments in Language Theory, 15th International Conference, DLT 2011, Lect. Notes in Comp. Sci., Vol. 6795, Springer, 2011, pp. 397-405.
  • E. Charlier, N. Rampersad, J. Shallit, Enumeration and decidable properties of automatic sequences, in G. Mauri and A. Leporati, eds., Developments in Language Theory, 15th International Conference, DLT 2011, Lect. Notes in Comp. Sci., Vol. 6795, Springer, 2011, pp. 165-179.
  • Janusz Brzozowski, Jeffrey Shallit, and Zhi Xu, Decision problems for convex languages, Information and Computation 209 (2011), 353-367. DOI link. Some of the algorithms in this paper can be considerably speeded up. For example, testing if a regular language is prefix-convex can be done as follows. Given an n-state DFA M, make an NFA M' with n+1 states by replacing the transition δ(p,a) = q with δ'(p,A) = q if p is an accepting state and δ'(p,N) = q if p is a nonaccepting state. Add a new accepting state p' and transitions from each accepting state p of the form δ(p,A) = p' and from each rejecting state q of the form δ(q,N) = p'. Then the set of strings accepted by M' is the record of the of states, accepting or not, encountered by processing all the strings of Σ^*. Now intersect this NFA with A⁺ N⁺ A⁺ to get M''. Then L(M) is not prefix-convex if and only if L(M'') is nonempty, which can be detected by depth-first search in O(n) time. The same trick can be used for suffix-convex, by first reversing the DFA M to get an NFA for the reversed language. Many of the other algorithms in our paper can be speeded up with this simple idea.
  • Narad Rampersad, Jeffrey Shallit, and Ming-wei Wang, Inverse star, borders, and palstars, Info. Proc. Letters 111 (2011), 420-422. DOI link.
  • Eric Rowland and Jeffrey Shallit, Avoiding 3/2-powers over the natural numbers, to appear, Discrete Mathematics (see above).
  • E. Charlier, M. Domaratzki, T. Harju, and J. Shallit, Finite orbits of language operations, in LATA 2011 conference proceedings.
    • accompanying data with machine-generated proofs
  • W. Elsberry and J. Shallit, Information theory, evolutionary computation, and Dembski's "complex specified information", Synthese 178 (2011), 237-270.

• 2010
  • J. F. Morgenbesser, J. Shallit, and T. Stoll, Thue-Morse at multiples of an integer, preprint, September 2010
  • N. Rampersad, J. Shallit, and M.-w. Wang, Inverse star, borders, and palstars, preprint, August 2010
  • J. Shallit and J. Stankewicz, Unbounded discrepancy in Frobenius numbers, preprint.
  • Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, and Jeffrey Shallit, Finding the growth rate of a regular or context-free language in polynomial time, Int. J. Found. Comput. Sci. 21 (4) (2010), 597-618.
  • N. Rampersad and J. Shallit, Detecting patterns in finite regular and context-free languages, Info. Proc. Letters 110 (2010), 108-112.

• 2009
  • M. Ackerman and J. Shallit, Efficient enumeration of words in regular languages, Theoret. Comput. Sci. 410 (2009), 3461-3470.
  • T. Ang, G. Pighizzini, N. Rampersad, and J. Shallit, Automata and reduced words in the free group, preprint, October 23 2009.
  • T. Ang and J. Shallit, "Length of the shortest word in the intersection of regular languages", Arxiv preprint, October 8 2009.
  • N. Rampersad, J. Shallit, and Z. Xu, The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages, Arxiv preprint, July 1 2009.
  • J. Shallit, Hamming distance for conjugates, Discrete Math. 309 (2009), 4197-4199.
  • (with L. B. Richmond) Counting abelian squares, Electronic J. Combinatorics 16 (1), #R72, June 2009.
  • N. Rampersad and J. Shallit, Detecting patterns in finite regular and context-free languages, preprint.
  • J.-P. Allouche and J. Shallit, The Tower of Hanoi and finite automata, to appear in the proceedings of the Symposium "La Tour d'Hanoï: Un casse-tête mathématique d'Édouard Lucas (1842-1891)".
  • J. Brzozowski, E. Grant, and J. Shallit, Closures in formal languages: concatenation, separation, and algorithms, submitted to DLT 2009.
  • J. Brzozowski, E. Grant, and J. Shallit, Closures in formal languages and Kuratowski's theorem, submitted to DLT 2009.
  • Mathieu Guay-Paquet and Jeffrey Shallit, Avoiding squares and overlaps over the natural numbers, Arxiv preprint. Appeared in Discrete Math. 309 (2009), 6245-6254.
  • D. Krieger, A. Miller, N. Rampersad, B. Ravikumar, and J. Shallit, Decimations of languages and state complexity, Theor. Comput. Sci. 410 (2009), 2401-2409.
  • (with T. Anderson, J. Loftus, N. Rampersad, N. Santean) Detecting palindromes, patterns, and borders in regular languages, Information and Computation 207 (2009), 1096-1118.
  • (with N. Rampersad, N. Santean, and B. Ravikumar), State complexity of unique rational operations, Theoret. Comput. Sci. 410 (2009), 2431-2441. DOI link
  • J.-P. Allouche, N. Rampersad, and J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence, Theoret. Comput. Sci. 410 (2009), 2795-2803.
  • J.-Y. Kao, Narad Rampersad, and J. Shallit, On NFAs where all states are final, initial, or both, Theoret. Comput. Sci. 410 (2009), 5010-5021.

• 2008
  • P. Ochem, N. Rampersad, and J. Shallit, Avoiding approximate squares, Int. J. Found. Comput. Sci. 19 (2008), 633-648. Available here. In this paper we should have cited an earlier paper of Beck, "An application of Lovasz local lemma: there exists a infinite 01-sequence containing no near identical intervals", in A. Hajnal, L. Lovász, and V. T. Sós, eds., Finite and Infinite Sets, Vol. I, Colloq. Math. Soc. Janos Bolyai. 37 (1981), 103-107.
  • (with Jui-Yi Kao, N. Rampersad, and Manuel Silva), Words avoiding repetitions in arithmetic progressions, Theoretical Computer Science, 391 (2008), 126--137; see here.
  • E. Grant, J. Shallit, and T. Stoll, Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin-Shapiro sequences, arxiv preprint, December 2008. Appeared in Acta Arithmetica 140 (2009), 345-368.
  • Yu-Hin Au and Jeffrey Shallit, Van der Waerden's theorem and avoidability in words, preprint, December 2008
  • (with D. Krieger), Maximal blocks in morphic and automatic words, preprint, August 2008.
  • (with J. Brzozowski and Z. Xu) Decision problems for convex languages, preprint, August 2008. To appear, LATA 2009.
  • (with J.-P. Allouche and N. Rampersad) Periodicity, repetitions, and orbits of an automatic sequence, preprint, August 2008.
  • (with L. B. Richmond) Counting abelian squares, preprint, July 2008.
  • (with Jui-Yi Kao and Zhi Xu) The Frobenius problem in a free monoid, STACS 2008, Bordeaux, France. pdf file.

• 2007
  • M. Domaratzki, A. Okhotin, and J. Shallit, Enumeration of context-free languages and related structures, J. Automata, Lang., & Combinatorics 12 (2007), 79-95.
  • J. Shallit, Hamming distance for conjugates, preprint, arXiv:0710.1234 [math.CO].
  • J.-P. Allouche, J. Shallit and J. Sondow, Summation of series defined by counting blocks of digits, J. Number Theory 123 (2007), 133-143. MR 90g:11013.
  • C. Epifanio, F. Mignosi, J. Shallit, and I. Venturini, On Sturmian graphs, Discrete Applied Math. 155 (2007), 1014-1030.

• 2006
  • (with Jui-Yi Kao, N. Rampersad, and Manuel Silva), "Words avoiding repetitions in arithmetic progressions", preprint available here.
  • (with J. Currie and N. Rampersad), "Binary words containing infinitely many overlaps", Electronic J. Combin., 13 (1) (2006), #R82.
  • (with S. Brown, N. Rampersad, and T. Vasiga), Squares and overlaps in the Thue-Morse sequence and some variants, RAIRO-Info. Theor. Appl. 40 (2006), 473-484.
  • (with G. Allouche and J.-P. Allouche), Kolams indiens, dessins sur le sables aux iles Vanuatu, courbe de Sierpinski, et morphismes de monoide, Annales de l'Institut Fourier 56 (2006), 2115-2130. Also available via Numdam.
    Erratum: There is a typographical error in the statement of Lemma 3.9. Instead of b(k,n) = 4^k·b(k,n-1) + (4^k-1)/3, it should be b(k,n) = 4^k·b(k,n-1) + n(4^k- 1)/3. Thanks to Gandhar Joshi for pointing this out.

• 2005
  • Michael Domaratzki, Keith Ellul, Jeffrey O. Shallit, and Ming-wei Wang, Non-uniqueness and radius of cyclic unary NFAs, Int. J. Found. Comput. Sci. 16 (5) (1995), 883-896.
  • The mathematics of Per Nørgård's rhythmic infinity system, Fibonacci Quarterly 43 (2005), 262-268.
  • (with K. Ellul, B. Krawetz, and M.-w. Wang) Regular expressions: new results and open problems, J. Autom. Lang. Combin. 10 (2005), 407-437.
    Note: many of the open problems in this paper have now been solved. Also please note that due to an editorial error at the journal, the journal previously published a preliminary draft in their 2004 volume. This latter version should not be cited; cite this 2005 version instead.
  • "Science, Pseudoscience, and the Three Stages of Truth", unpublished manuscript, March 28 2005, pdf
  • L. Ilie, P. Ochem and J. Shallit, A generalization of repetition threshold, Theoret. Comput. Sci. 345 (2005), 359-369.
  • B. Krawetz, J. Lawrence, and J. Shallit, "State Complexity and the Monoid of Transformations of a Finite Set", in Implementation and Application of Automata, Lecture Notes in Computer Science, Vol. 3317, 2005, pp. 213-224. Final version in Int'l J. Found. Comput. Sci. 16 (2005), 547-563.
  • (with N. Rampersad), "Words avoiding reversed subwords", J. Combin. Math. Combin. Comput., 54 (2005), 157-164. pdf
  • N. Rampersad, J. Shallit, and M.-w. Wang, Avoiding large squares in infinite binary words, Theoret. Comput. Sci. 339 (2005), 19-34.
  • J.-P. Allouche, N. Rampersad, and J. Shallit, On integer sequences whose first iterates are linear, Aequationes Math. 69 (2005), 114-127.
  • J.-P. Allouche, J. Shallit, and G. Skordev, Self-generating sets, integers with missing blocks, and substitutions, Discrete Math. 292 (2005), 1-15.
  • (with J. Lee), "Enumerating regular expressions and their languages", to appear, Proc. of CIAA 2004, LNCS 3317, 2005, pages 2-22. Here is a link to the conference version. Also see the directory of Maple worksheets that accompanies this paper.
  • (with Peter Russell), "Ulexite or Satin Spar Gypsum? The Scoop on "Television Stone", in Chem 13 News, Number 326 (January 2005), pp. 16-17.

• 2004
  • (with C. Epifanio, F. Mignosi, and I. Venturini) Sturmian graphs and a conjecture of Moser, in Developments in Language Theory, Springer Lecture Notes in Computer Science, Vol. 3340, 2004, pp. 175-187.
  • (with W. Elsberry) Playing games with probability: Dembski's complex specified information, in Why Intelligent Design Fails: A Scientific Critique of the New Creationism, Rutgers University Press, 2004, pp. 121-138.
  • J. Shallit, Formal languages and number theory, in M. B. Nathanson, ed., Unusual Applications of Number Theory, Proc. DIMACS Workshop January 10-14, 2000, American Mathematical Society, 2004, pp. 169-181.
  • J. Shallit, Simultaneous avoidance of large squares and fractional powers in infinite binary words, Int'l. J. Found. Comput. Sci. 15 (2004), 317-327. You can also look at the arxiv preprint.
  • J. Karhumäki and J. Shallit, Polynomial versus exponential growth in repetition-free binary words, J. Combinatorial Theory Ser. A 105 (2004), 335-347. You can also look at the arxiv version.
    • A Pascal program that verifies some of the assertions in the paper
    • A Maple program that verifies some of the assertions in the paper. You will also need the DAVID_IAN package from Doron Zeilberger's home page.
  • (with Troy Vasiga) On the iteration of certain quadratic maps over GF(p), Discrete Math. 277 (2004), 219-240. Note: our results were improved by Chou and Shparlinskii, On the cycle structure of repeated exponentiation modulo a prime, J. Number Theory 107 (2004), 345-356.

• 2003
  • (with Jean-Paul Allouche) The ring of k-regular sequences, II, Theoret. Comput. Sci. 307 (2003), 3-29. Corrigendum: on page 24, in Example 25, 7 o 1 should be 7, not 8.
  • (with S. Cautis, F. Mignosi, M.-w. Wang, and S. Yazdani) Periodicity, morphisms, and matrices, Theoret. Comput. Sci. 295 (2003), 107-121.
  • (with W. Elsberry), Eight challenges for intelligent design advocates, Reports of the NCSE 23 No. 5-6, (Sept.-Dec. 2003), 23-25.
  • The story of an ID urban legend, Reports of the NCSE 23 No. 5-6, (Sept-Dec. 2003), 39.
  • (with N. Rampersad) Words avoiding reversed subwords, arxiv preprint arXiv:math/0311121 [math.CO], November 7 2003.
  • (with W. Elsberry) Information theory, evolutionary computation, and Dembski's "complex specified information"
  • (with L. Ilie) A generalization of repetition threshold, arxiv preprint arXiv:math/0310144 [math.CO], October 10 2003.
  • B. Krawetz, J. Lawrence, and J. Shallit, State complexity and the monoid of transformations of a finite set, arxiv preprint arXiv:math/0306416 [math.GR], December 9 2003.
  • (with N. Rampersad and M.-w. Wang) Avoiding large squares in infinite binary words, arxiv preprint arXiv:math/0306081, June 4 2003.
  • What this country needs is an 18-cent piece, Math. Intelligencer 25 (2) (2003), 20-23. pdf
  
  This paper generated a lot of media and blogger attention. Not everybody realized that the 18-cent suggestion was tongue-in-cheek. See
  • Ivars Peterson's article in Science News
  • Nature Science Update by Philip Ball
  • Globe and Mail
  • NPR's Wait, Wait, Don't Tell Me, May 31 2003. (start listening at 12:50)
  • Forbes Magazine, June 23 2003 (registration required)
  • Amusing commentary from Laurel Wellman in the San Francisco Chronicle
  • slashdot commentary
  • Discover Magazine, Vol. 24, No. 10, October 2003, pp. 28-29.
  • Yes Mag (Canada's Science Magazine for Kids), No. 37, Nov/Dec 2003, p. 5
  • It was featured on the youtube channel Stand-up Maths with Matt Parker in 2025.
  I recently learned that Tom Young at Spring Lake Senior High School in Spring Lake Park, Minnesota, made a similar suggestion in 1995. See here for the article.

  Waterloo undergraduate Ray Kuo made the following nice graphic illustrating my hypothetical Canadian 83-cent coin, with the University of Waterloo's Math and Computer Building on one side. It's reproduced here with his permission.
  Several people wanted more details about the optimal systems for Canada. Here's what I've computed. For amounts up to $5.00, Canadians use the following denominations: 1 cent, 5 cents, 10 cents, 25 cents, 100 cents, 200 cents. The expected number of coins per transaction is 5.9. The optimal 4-coin system is (1,7,57,80), with an expected 6.804 coins per transaction. The optimal 5-coin system is (1,6,20,85,121) with an expected 5.44 coins per transaction. The optimal 6-coin systems are (1,6,14,62,99,140) and (1,8,13,69,110,160), each of which give an expected 4.67 coins per transaction.

  For the greedy algorithm, I obtained the following results. The optimal 4-coin systems are (1,5,23,109) and (1,5,23,110), with an expected 7.176 coins per transaction (as compared to 5.9 with the current 6-coin system). The optimal 5-coin systems are (1,4,13,44,147), (1,4,13,44,150), (1,4,14,47,160), and (1,4,14,48,160) with an expected cost of 5.816 coins per transaction. The optimal 6-coin systems are (1,3,8,26,64,{202 or 203 or 204}) and (1,3,10,25,79,{195 or 196 or 197}) with an expected cost of 5.036 coins per transaction.

  Note added October 23, 2003: Both Europe and China use a system of denominations based on the recurring pattern

  1,2,5,  10,20,50,  100,200,500, ... 
  

  This may seem natural, but a small change to

  1,3,4,  10,30,40,  100,300,400, ...
  

  would significantly decrease the average number of coins per transaction. This new system has the following advantages:
  • Change can still be made on a digit-by-digit basis. For example, to make change for 348, first do the hundreds digit (getting 300), then the tens (getting 40), and then the ones (getting 4+4).
  • The greedy algorithm can be used in all cases but one. The exception is that 6 = 3+3 and not 4+1+1. (Similarly, 60 = 30+30, etc.)
  • Assuming the uniform distribution of change denominations, on all scales (10, 100, 1000, etc.) the new system is about 6% better.
  • If one assumes change denominations are distributed by Benford's law, the new system is about 7% better up to 10, about 6% better up to 100, and about 6% better up to 1000.
  
  
• 2002
  • M. Domaratzki, D. Kisman, and J. Shallit, On the number of distinct languages accepted by finite automata with n states J. Autom. Lang. Comb. 7 (2002), 469-486.
    Unary NFA languages with
    • 2 states
    • 3 states
    • 4 states
    • 5 states
  • G. Pighizzini, J. Shallit, and M.-w. Wang, Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds, J. Comput. System Sci. 65 (2002), 393-414.
  • (with J. Ellis and H. Fan) The cycles of the multiway perfect shuffle permutation, Discrete Mathematics & Theoretical Computer Science 5 (2002), 169-180.
  • (with G. Pighizzini), Unary language operations, state complexity, and Jacobsthal's function, Int'l. J. Found. Comput. Sci. 13 (2002), 145-159.
  • Simulating finite automata with context-free grammars, Info. Proc. Letters 84 (2002), 339-344.
  • The computational complexity of the local postage stamp problem, SIGACT News 33 (1) (March 2002), 90-94.
  • (with Ming-wei Wang), On two-sided infinite fixed points of morphisms, Theoret. Comput. Sci. 270 (2002), 659-675.
  
  
• 2001
  • M. Domaratzki, J. Shallit, and S. Yu, Minimal covers of formal languages, in Kuich, W., Rozenberg, G., Salomaa, A. (eds) Developments in Language Theory. DLT 2001. Lecture Notes in Computer Science, vol. 2295. Springer, Berlin, Heidelberg, pp. 319-329.
  • Calvin College hosts "design" conference, in NCSE Reports 21 Nos. 1-2, (Jan-Apr 2001), pp. 4-5. (Critical review of "intelligent design" conference.)
  • (with Ming-wei Wang), Automatic complexity of strings, J. Autom. Lang. Combinat. 6 (2001), 537-554.
    • pdf
  • (with Ming-wei Wang) Weakly self-avoiding words and a construction of Friedman, Electronic J. Combinatorics 8 (1) (2001), N2.
    
  • State complexity and Jacobsthal's function, in S. Yu and A. Paun, eds., Implementation and Application of Automata (CIAA 2000), Lecture Notes in Computer Science, Vol. 2088, Springer, 2001, pp. 272-278.
  
  
• 2000
  • George Boros, Victor Moll, and Jeffrey Shallit The 2-adic valuation of the coefficients of a polynomial, Scientia Ser. A: Math. Sci. 7 (2000-1), 47-60. Note: one of the conjectures in our paper was proved in John B. Little, On the zeroes of two families of polynomials arising from certain rational integrals, Rocky Mountain J. Math. 35 (2005), 1205-1215.
  • Charles Lam, Jeffrey Shallit, and Scott Vanstone, Worst-case analysis of an algorithm for computing the greatest common divisor of n inputs, in J. Buchmann et al., eds., Coding Theory, Cryptography and Related Areas, Springer-Verlag, 2000, pp. 156-166.
  • Minimal primes, J. Recreational Mathematics 30 (2) (1999-2000), 113-117.
  • Automaticity and rationality, J. Automata, Languages, and Combinatorics 5 (2000), 255-268.
  • Jean-Paul Allouche and J. Shallit, Sums of digits, overlaps, and palindromes, Discrete Math. and Theoretical Computer Science, 4 (2000), 1-10.
  • J. Loftus, J. Shallit, and M.-w. Wang, New problems of pattern avoidance, in G. Rozenberg and W. Thomas, eds., Developments in Language Theory (DLT '99), World Scientific Press, 2000, pp. 185-199.
  
  
• 1999
  • J. F. Buss, G. S. Frandsen, and J. O. Shallit, The computational complexity of some problems of linear algebra, J. Comput. System Sci. 58 (1999), 572-596.
  • M. Mendès France, A. J. van der Poorten, and J. Shallit, On lacunary formal power series and their continued fraction expansion, in K. Gyory, H. Iwaniec, and J. Urbanowicz, eds., Number Theory in Progress, de Gruyter, 1999, pp. 321-326.
  • Jean-Paul Allouche and J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in C. Ding. T. Helleseth, and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16. pdf version
  • (with David Swart) An efficient algorithm for computing the i'th letter of ϕⁿ (a), Proc. 10th Annual SODA conference, 1999, pp. 768-775.
  • M.-w. Wang and J. Shallit, An inequality for non-negative matrices, Linear Alg. Applications 290 (1999), 135-144.
  • (with M.-w. Wang) On two-sided infinite fixed points of morphisms, Proc. 12th FCT Conference, Iasi, Romania, 1999, Lecture Notes in Computer Science #1684, pp. 488-499.
  • (with J. Currie, H. Petersen, and J. M. Robson) Separating words with small grammars, J. Automata, Languages, and Combinatorics 4 (1999), 101-110.
  • Number theory and formal languages, in D. A. Hejhal, J. Friedman, M. C. Gutzwiller, and A. M. Odlyzko, eds., Emerging Applications of Number Theory, IMA Volumes in Mathematics and Its Applications, V. 109, Springer-Verlag, 1999, pp. 547-570.
  • (with Dave Hamm) Characterization of finite and one-sided infinite fixed points of morphisms on free monoids, University of Waterloo, Technical report Technical Report CS-99-17, July 1999.
  
  
• 1998
  • Charles Lam, Jeffrey Shallit, and Scott Vanstone, Worst-case analysis of an algorithm for computing the greatest common divisor of n inputs, University of Waterloo, Department of Computer Science, Technical report CS-98-01, January 1998.
  • Jean-Paul Allouche and Jeffrey Shallit, Generalized perturbed symmetry, Europ. J. Combinatorics 19 (1998), 401-411.
  • (with Ian Glaister) Automaticity III: Polynomial automaticity and context-free languages, computational complexity 7 (1998), 371-387.
  • (with M.-w. Wang) On minimal words with given subword complexity Electronic Journal of Combinatorics 5(1) (1998), #R35.
  • J.-P. Allouche, J. Currie, and J. Shallit, Extremal infinite overlap-free binary words, Electronic Journal of Combinatorics 5(1) (1998), #R27.
  
  
• 1997
  • J. Shallit and H. Lyons, Social issues of networking in Canada's information society, The Information Society 13 (2) (1997), 147-151. This was an introduction to a special issue devoted to the proceedings of the Symposium on Free Speech and Privacy held at the University of Waterloo, November 26 1994.
  • J.-P. Allouche, E. Cateland, W. J. Gilbert, H.-O. Peitgen, J. Shallit, and G. Skordev, Automatic maps in exotic numeration systems, Theory Comput. Syst. 30 (1997), 285-331.
  • (with J. F. Buss and G. S. Frandsen) The computational complexity of some problems of linear algebra. For the conference version in Proc. 14th Symp. Theor. Aspects of Computer Sci. (STACS 97), Springer-Verlag, Lecture Notes in Computer Sci. Vol. 1200, pp. 451-462, go here.
  • (with J. C. Lagarias) Linear fractional transformations of continued fractions with bounded partial quotients. Appeared in Journal de Théorie des Nombres de Bordeaux 9 (1997), 267-279. Corrigendum 15 (2003), 741-743.
  • C. Pomerance, J. M. Robson, and J. Shallit, Automaticity II: Descriptional complexity in the unary case, Theoret. Comput. Sci. 180 (1997), 181-201.
  
  
• 1996
  • J. Buss, G. Frandsen, and J. Shallit, The computational complexity of some problems of linear algebra, BRICS Technical Report RS-96-33, Basic Research in Computer Science, September 1996.
  • E. Bach, R. Lukes, J. Shallit, and H. C. Williams, Results and estimates on pseudopowers, Math. Comp. 65 (1996), 1737-1747.
  • (with I. Glaister), "Polynomial automaticity, context-free languages, and fixed points of morphisms", in Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 1113, 1996, pp. 382-393.
  • La machine à congruences, La Revue no. 14, March 1996, pp. 14-19.
  • (with J.-P. Allouche, A. Lubiw, M. Mendès France, and A. J. van der Poorten) Convergents of folded continued fractions, Acta Arithmetica 77 (1996), 77-96. Corrigenda: (a) in the very first line a_k should be b_k. (b) the recursion formula in Theorem 10 on page 85 is not quite right. The formula as written fails for n = 2. We need to add a special case. For n = 2 the polynomial in question is e₁ e₂ X² + 1.
  • S. Lehr, J. Shallit, and J. Tromp, On the vector space of the automatic reals, Theoret. Comput. Sci. 163 (1996), 193-210.
  • J. Shallit and Y. Breitbart, Automaticity I: Properties of a measure of descriptional complexity, J. Comput. System Sci. 53 (1996), 10-25.
  • Automaticity IV: Sequences, Sets, and Diversity. Appeared in J. Théorie Nombres Bordeaux 8 (1996), 347-367.
  • (with E. Bach, R. Lukes, and H. C. Williams) Some results and estimates on pseudopowers. Appeared in Mathematics of Computation 65 (1996), 1737-1747.
  • Ian Glaister and Jeffrey Shallit, A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters 59 (1996), 75-77.
  
  
• 1995
  • F. Morain, J. Shallit, and H. Williams, Discovery of a lost factoring machine. Appeared in Math. Intelligencer 17 (3) (Summer 1995), 41-47. Available at https://doi.org/10.1007/BF03024369. Also see Ivars Peterson's article in Science News, October 1 1994.
  • J. Tromp and J. Shallit, Subword complexity of the generalized Thue-Morse word, Information Processing Letters 54 (1995), 313-316.
  • J.-P. Allouche, E. Cateland, H.-O. Peitgen, G. Skordev, and J. Shallit, Automatic maps on a semiring with digits, Symposium in Honor of Benoit Mandelbrot (Curaçao, 1995) Fractals 3 (1995), no. 4, 663-677. Also appeared in a separate volume, published by World Scientific Press, entitled Fractal Geometry and Analysis, 1996.
  
  
• 1994
  • H. C. Williams and J. O. Shallit, Factoring integers before computers, in Proc. Symp. Appl. Math. 48 (1994), 481-531.
  • J.-P. Allouche, D. Astoorian, J. Randall, and J. Shallit, Morphisms, squarefree strings, and the Tower of Hanoi puzzle, Amer. Math. Monthly 101 (1994), 651-658. Also available via JSTOR.
  • J. Shallit and J. Sorenson, Analysis of a left-shift binary gcd algorithm, in Adleman, L.M., Huang, MD. (eds) Algorithmic Number Theory. ANTS 1994. Lecture Notes in Computer Science, vol. 877. Springer, pp. 169-183. Full version appeared in J. Symbolic Computation 17 (1994), 473-486.
  • P. Enflo, A. Granville, J. Shallit, and S. Yu, On sparse languages L such that LL = Σ^*, Discrete Appl. Math. 52 (1994), 275-285.
  • J. Shallit, Origins of the analysis of the Euclidean algorithm, Historia Mathematica 21 (1994), 401-419.
    • The reader may want to look at P. Schreiber's followup paper in Historia Mathematica 22 (1995), 422-424.
  • J. Shallit, Numeration systems, linear recurrences, and regular sets, Information and Computation 113 (1994), 331-347.
  • A minimization problem, Problem 94-15, SIAM Review 36 (3) (1994) 490-491. Solution in SIAM Review 37 (3) (1995), 451-458.
  • Pierce expansions and rules for the determination of leap years, Fibonacci Quart. 32 (1994), 416-423.
  • (with Yuri Breitbart), "Automaticity: Properties of a measure of descriptional complexity", in Proc. STACS 94, Lecture Notes in Computer Science, Vol. 775 (1994), pp. 619-630. This is the conference version of the paper; the full version was published in 1996
  
  
• 1993
  • J.-P. Allouche and J. O. Shallit, Complexité des suites de Rudin-Shapiro généralisées, J. Théorie Nombres Bordeaux 5 (1993), 283-302.
  • A. J. van der Poorten and J. Shallit, A specialised continued fraction, Canad. J. Math. 45 (1993), 1067-1079.
  • E. Bach, J. Driscoll, and J. Shallit, Factor refinement, J. Algorithms 15 (1993), 199-222.
  • Rational numbers with non-terminating, non-periodic modified Engel-type expansions, Fibonacci Quarterly 31 (1993), 37-40.
  • (with H. W. Lenstra, Jr.) Continued fractions and linear recurrences, Mathematics of Computation 61 (1993), 351-354. Since then, other proofs were found by J.-P. Bézivin, Fractions continues et suites récurrentes, C. R. Acad. Sci. Paris, Série I, Mathématiques, 318 (1994), 991-994.
  • On the maximum number of distinct factors in a binary string, Graphs and Combinatorics 9 (1993), 197-200.
  • J. Shallit and J. Sorenson, A binary algorithm for the Jacobi symbol, ACM Sigsam Bulletin 27 (1) (January 1993), 4-11.
  
  
• 1992
  • A. J. van der Poorten and J. Shallit, Folded continued fractions, J. Number Theory 40 (1992), 237-250.
  • J. Shallit, Real numbers with bounded partial quotients: a survey, L'Enseignement Math. 38 (1992), 151-187. pdf copy.
  • J.-P. Allouche, P. Morton, and J. Shallit, Pattern spectra, substring enumeration, and automatic sequences, Theor. Comput. Sci. 94 (1992), 161-174.
  • Andrew Szilard, Sheng Yu, Kaizhong Zhang, Jeffrey Shallit, Characterizing regular languages with polynomial densities, in I. M. Havel and V. Koubek, eds., MFCS 1992, Lect. Notes in Computer Sci., Vol. 629, pp. 494-503.
  • Balanced binary representations. This is a paper that I never tried to publish. It is not in final form, to say the least, but since others have referred to it I decided to make it available.
    • In pdf format
  • (with David Wilson) The "3x+1" problem and finite automata, Bulletin of the EATCS, No. 46 (February 1992), 182-185. pdf version.
  • The ring of k-regular sequences, Theoret. Comput. Sci. 98 (1992), 163-197. [This on-line version is a preprint that differs slightly from the version actually published.] Corrigendum: in the published version, at the top of page 191, line 4, in the definition of g(X) replace b(∞, n) with b(∞, 2n).
    Corrigendum: Eric Rowland points out that the proof of Theorem 2.7 is incomplete. The given construction only works when a and k are relatively prime. Here are two different ways to prove the result.
  • Randomized algorithms in "primitive" cultures, or what is the oracle complexity of a dead chicken?, ACM SIGACT News Volume 23, Issue 4 (Fall 1992), 77-80. Follow-up letter to the editor here.
  
  
• 1991
  • J. Shallit, Description of generalized continued fractions by finite automata, Faculty of Mathematics Research Report CS-91-44, September 1991.
  • J. Shallit, On the maximum number of distinct factors of a binary string, Faculty of Mathematics Research Report CS-91-31, July 1991.
  • J. Shallit, Rational numbers with non-terminating, non-recurring modified Engel-type expansions, University of Waterloo Computer Science Department, Research Report CS-91-13, April 1991.
  • J. L. Davison and J. O. Shallit, Continued fractions for some alternating series, Monatshefte Math. 111 (1991), 119-126.
  • Some facts about continued fractions that should be better known, University of Waterloo, Technical Report #30, 1991.
  • (with Paul Erdös) "New bounds on the length of finite Pierce and Engel series", J. Théorie Nombres Bordeaux 3 (1) (1991), 43-53.
  • Characteristic words as fixed points of homomorphisms, University of Waterloo Technical Report CS-91-72, 1991.
  • Quickie Q785, Mathematics Magazine, 64 (5) (1991), 351, 357. My two-line proof that C + C = [0,2], where C is the Cantor middle-thirds set.

• 1990
  • J. Shallit, On the worst case of three algorithms for computing the Jacobi symbol, J. Symbolic Computation 10 (1990), 593-610.
  • J.-P. Allouche and J. Shallit, Sums of digits and the Hurwitz zeta function, In: Nagasaka, K., Fouvry, E. (eds) Analytic Number Theory. Lecture Notes in Mathematics, vol. 1434. Springer, 1990, pp. 19-30.
  
  
• 1989
  • J. Shallit, Letter to the editor, Fib. Quart. 27 (1989), 186.
  • E. Bach, J. Driscoll, and J. Shallit, Factor refinement, Computer Sciences Technical Report #883, University of Wisconsin-Madison, October 1989
  • J.-P. Allouche, J. Betrema, and J. O. Shallit, Sur des points fixes de morphismes d'un monoïde libre, RAIRO Info. Théor. Appl. 23 (1989), 235-249. Also available through numdam.

    We failed to mention an earlier occurrence of the numeration system in the paper based on 2ⁱ – 1: namely, E. W. Myers, An applicative random-access stack, Information Processing Letters 17 (1983), 241-248.

  • M. Mendès France and J. Shallit, Wire bending, J. Combinatorial Theory Ser. A 50 (1989), 1-23.
  • J.-P. Allouche, P. Hajnal, and J. O. Shallit, Analysis of an infinite product algorithm, SIAM J. Disc. Math. 2 (1989), 1-15.
  • J. Shallit and J. Stolfi, Two methods for generating fractals, Computers & Graphics 13 (1989), 185-191.
  • E. Bach and J. Shallit, Factoring with cyclotomic polynomials, Math. Comp. 52 (1989), 201-219.
  • J.-P. Allouche and J. Shallit, Infinite products associated with counting blocks in binary strings, J. London Math. Soc. 39 (1989), 193-204.
  
  
• 1988
  • D. Rubinstein, J. Shallit, and M. Szegedy, A subset coloring algorithm and its applications to computer graphics, Commun. ACM 31 (1988), 1228-1232.
  • A generalization of automatic sequences, Theoret. Comput. Sci. 61 (1988), 1-16. Corrigenda:
    • On p.7, insert after "limit sequence" the following: lim_{i → ∞}.
    • On p.7, by "commute with ϕ" I should have said, "i.e., λ(ϕ^j (a)) = ϕ^j(λ(a)) for all j".
    • On p.12, in Example 2, the equation for X(n + 1) should have the argument n – 1 and not n.
    • On p.13, just before Example 3, the summation should start at 0 and not 1.
  • J. Shallit, Fractals, bitmaps, and APL, APL Quote Quad 18 (3) (March 1988), 24-32.
  
  
• 1987
  • J. O. Shallit, Automates finis, pliage de fil de fer, et fractions continues, Séminaire de Théorie des Nombres de Bordeaux, (1986-1987), pp. 38:1-38:13.
  • (with J.-P. Allouche, H. Cohen, and M. Mendès France) De nouveaux curieux produits infinis, Acta Arithmetica 49 (1987), 141-153.
  
  
• 1986
  • Appendix to the paper of Salon, Séminaire de Théorie des Nombres de Bordeaux, 1986-7, pp. 04:29A--04:36A.
    Corrigendum: in Example 7, p. 04-33-A, in the image of ϕ₇(12), the "7" needs to be replaced by "17".
  • J. Shallit, Metric theory of Pierce expansions, Fibonacci Quart. 24 (1986), 22-40.
  • E. Bach, G. Miller, and J. Shallit, Sums of divisors, perfect numbers, and factoring, SIAM J. Comput. 15 (1986), 1143-1154.
  • Michael Rabin and Jeffrey Shallit, Randomized algorithms in number theory, Commun. Pure Appl. Math. 39 (1986), S239-S256. [The "S" in the page numbers refers to a special issue of the journal which is sometimes difficult to find. There are some typos, like the correct spelling of my first name, and on page S241, the binary representation of 2k should be 2k = 2^d₁ + ... + 2^d_m.]
  
  
• 1985
  • J. Shallit, Sur la complexité des fonctions arithmétiques, Séminaire de Théorie des Nombres de Bordeaux, 1985-6, exposé no. 1, 1:01-1:06.
  • E. Bach and J. Shallit, Factoring with cyclotomic polynomials, in 26th FOCS (Foundations of Computer Science), IEEE Press, 1985, pp. 443-450. Full version published in 1989 (above).
  • J. Shallit and A. Shamir, Number-theoretic functions which are equivalent to number of divisors, Info. Proc. Letters 20 (1985), 151-153.
  • J. Shallit, Sur certains produits liés aux sommes des chiffres, Groupe d'étude en théorie analytique des nombres, tome 2 (1985-1986), exp. no. 3, pp. 1-5.
  • On infinite products associated with sums of digits, J. Number Theory 21 (1985), 128-134.
  
  
• 1984
  • Some predictable Pierce expansions, Fibonacci Quarterly 22 (1984), 332-335.
  • E. Bach and J. Shallit, A class of functions equivalent to factoring, University of Chicago, Technical Report 84-008, December 1984.
  • An exposition of Pollard's algorithm for quadratic congruences, University of Chicago Technical Report 84-006, 1984.
  
  
• 1983
  • (with John F. Hughes), On the number of multiplicative partitions, Amer. Math. Monthly 90 (1983), 468-471. One of the conjectures in this paper was resolved by Dodd and Mattics, A bound for the number of multiplicative partitions, Amer. Math. Monthly 93 (1986), 125-126. Another was also resolved by Dodd and Mattics, Estimating the number of multiplicative partitions, Rocky Mtn. J. Math. 17 (1987), 797-813. Also see Hui-Zhong Cao, On the number of multiplicative partitions, J. Combin. Math. Combin. Comput. 7 (1990), 218-221, and Hui-Zhong Cao, Essentially different factorizations of a natural number, Compositio Math. 77 (1991), 343-346. The true asymptotic behavior of the function we studied was found by Canfield et al., On a problem of Oppenheim concerning "factorisatio numerorum", J. Number Theory 17 (1983), 1-28.
  • Merrily we roll along: some aspects of ?", in APL 83 Conference Proceedings, pp. 243-249.
  
  
• 1982
  • J. O. Shallit, Simple continued fractions for some irrational numbers, II J. Number Theory 14 (1982), 228-231.
  • V-partitions and permutations by inversions, in APL Quote Quad 12 (3) (March 1982), 15-17.
  • Computational simplicial homology in APL, in W. H. Janko and W. Stucky, APL 82 Conference Proceedings, APL Quote Quad 13 (1) (1982), pp. 332-338. Reproduced courtesy of ACM.
  
  
• 1981
  • Infinite arrays and diagonalization, in APL 81 Conference Proceedings, pp. 281-285. Reproduced courtesy of ACM.
  
  
• 1980
  • Extending APL to infinity, in G. A. van der Linden, ed., Proc. APL 80 Conference, North-Holland, 1980, pp. 123-132.
  • A Triangle for the Bell numbers, in V. E. Hoggatt, Jr. and M. Bicknell-Johnson, A Collection of Manuscripts Related to the Fibonacci Sequence, 1980, pp. 69-71.

• 1979
  • "Integer functions and continued fractions", AB Thesis, Department of Mathematics, Princeton University, April 15 1979. Part 1; Part 2. This was my undergraduate thesis. Much of it is trivial and not so interesting today, except perhaps as juvenalia. However, the main result, Theorem II.3.3, p. 58 of the second part, remains of interest. Although the result is stated there using a context-free grammar, the grammar is linear and hence the result would be better stated using a finite automaton. Eventually I plan to publish an abbreviated version of this.
  • J. O. Shallit, Simple continued fractions for some irrational numbers, Journal of Number Theory 11 (1979), 209-217. pdf
  • An algorithm for field operations on complex numbers, unpublished manuscript, published c. 1979. This bit of juvenalia, written before I knew anything about resultants, was submitted to a journal and rightly rejected. It was originally written in troff and I converted it using tr2latex. I put it here because the question continues to be of interest; see, e.g., here.

• 1978
  • David Rosen and Jeffrey Shallit, A continued fraction algorithm for approximating all real polynomial roots, Math. Magazine 51 (1978), 112-116.

• 1976
  • The prime factorization of 1. Appeared in APL Quote Quad, Vol. 6, No. 4 (Winter 1976), 36-37.
  • Predictable regular continued cotangent expansions, J. Research Nat. Bureau Standards 80B (1976), 285--290. My first paper with a genuinely new research result.
    • Erratum: in the second equation on p. 287, the "5" in the exponent should, of course, be an "s".

• 1975
  • A simple proof that phi is irrational, Fibonacci Quarterly 13 (1975), 32. My first published paper. I include this bit of juvenalia just for completeness.
  • J. Shallit, An interesting continued fraction, Math. Magazine 48 (1975), 207-211. Actually not that interesting!

E-mail: