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.

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

A partial list of my co-authors is here.

• 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.
  • 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. Available at https://doi.org/10.1016/j.tcs.2023.114363.
  • Jeffrey Shallit, Rarefied Thue-Morse sums via automata theory and logic, J. Number Theory 257 (2024) 98-111. Available at https://doi.org/10.1016/j.jnt.2023.10.015.
  • 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.

• 2023
  • 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 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.
  • 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, Note on a Fibonacci parity sequence, Cryptography and Communications 15 (2023), 309-315.
  • L. Schaeffer and J. Shallit, The first-order theory of binary overlap-free words is decidable, Canad. J. Math. (2023).
    • 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.
  • 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-Theor. 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.
  • 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.
  • 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-Theor. 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.
  • 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.
  • 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
  • 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. 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
  • 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.

    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.

• 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.
  • 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 Mercas R., Reidenbach D. (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. In Mercas R., Reidenbach D. (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 Mercas R., Reidenbach D. (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 Mercas R., Reidenbach D. (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.
  • 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. Erratum: 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, 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, Jeffrey Shallit: Automatic Theorem-Proving in Combinatorics on Words. Int. J. Found. Comput. Sci. 24 (6) (2013), 781-798.
    Erratum: 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. Errata 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. doi

• 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. Erratum: 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. link

• 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, Jeffrey Shallit: Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time. Int. J. Found. Comput. Sci. 21(4): 597-618 (2010)

• 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", 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", 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", 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
  • (with J.-P. Allouche and N. Rampersad) "Periodicity, repetitions, and orbits of an automatic sequence", Theoret. Comput. Sci. 410 (2009), 2795-2803.
  • (with J.-Y. Kao and Narad Rampersad), "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, 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
  • J. Shallit, "Hamming Distance for Conjugates", preprint. To appear, Discrete Math.
  • J.-P. Allouche, J. Shallit and J. Sondow, "Summation of series defined by counting blocks of digits", J. Number Theory 123 (2007), 133-143.
  • 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. 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
  • 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. preprint version. 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.
  • "Science, Pseudoscience, and the Three Stages of Truth", unpublished manuscript, March 28 2005, pdf
  • (with P. Ochem and L. Ilie), "A generalization of repetition threshhold", Theoret. Comput. Sci. 345 (2005), 359-369.
  • (with B. Krawetz and J. Lawrence), "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.
  • (with N. Rampersad), "Words avoiding reversed subwords", J. Combin. Math. Combin. Comput., 54 (2005), 157-164. pdf
  • (with N. Rampersad and M.-w. Wang), "Avoiding large squares in infinite binary words", Theoret. Comput. Sci. 339 (2005), 19-34.
  • (with J.-P. Allouche and N. Rampersad), "On integer sequences whose first iterates are linear", Aequationes Math. 69 (2005), 114-127.
  • (with J.-P. Allouche 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 3314, 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.
  • 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.
  • Simultaneous avoidance of large squares and fractional powers in infinite binary words, Int'l. J. Found. Comput. Sci. 15 (2004), 317-327.
  • (with J. Karhumäki) Polynomial versus exponential growth in repetition-free binary words, J. Combinatorial Theory Ser. A 105 (2004), 335-347.
    • 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.

• 2003
  • (with Jean-Paul Allouche) The ring of k-regular sequences, II, Theoret. Comput. Sci. 307 (2003), 3-29. Erratum: 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
  • (with W. Elsberry) Information theory, evolutionary computation, and Dembski's "complex specified information"
  • (with L. Ilie) A generalization of repetition threshold
  • (with B. Krawetz and J. Lawrence) State complexity and the monoid of transformations of a finite set
  • (with N. Rampersad and M.-w. Wang) Avoiding large squares in infinite binary words
  • 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 Math Trek or his article in Science News
    • Nature Science Update
    • Globe and Mail
    • NPR's Wait, Wait, Don't Tell Me (click on "Listen to the whole show", and start listening at 11:53)
    • Forbes Magazine, June 23 2003 (registration required)
    • Toronto Star
    • UW Imprint
    • Ottawa Citizen
    • Amusing commentary from Laurel Wellman in the San Francisco Chronicle
    • slashdot commentary
    • Discover Magazine article, October 2003
    • Yes Mag (Canada's Science Magazine for Kids), Nov/Dec 2003, p. 5
    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
  • (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
  • 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, to appear in J. Autom. Lang. Combinat..
    • pdf
  • (with M. Domaratzki and D. Kisman), On the number of distinct languages accepted by finite automata with n states (Final version appeared in J. Autom. Lang. Comb. 7 (2002), 469-486.
    Unary NFA languages with
    • 2 states
    • 3 states
    • 4 states
    • 5 states
  • (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, V. 2088, Springer, 2001, pp. 272-278. (Note: The link will work only if you have a subscription to Springer.)
  
  
• 2000
  • Minimal primes, J. Recreational Mathematics 30 (2) (1999-2000), 113-117.
  • Automaticity and rationality, J. Automata, Languages, and Combinatorics 5 (2000), 255-268.
  • (with Jean-Paul Allouche) Sums of digits, overlaps, and palindromes, Discrete Math. and Theoretical Computer Science, 4 (2000), 1-10.
  • (with J. Loftus 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, pp. 185-199.
  
  
• 1999
  • (with Jean-Paul Allouche) 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 phi^n (a), appeared in Proc. 10th Annual SODA conference, 1999, pp. 768-775.
  • (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
  • 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.
  • (with J.-P. Allouche and J. Currie) Extremal Infinite Overlap-Free Binary Words, Electronic Journal of Combinatorics 5(1) (1998), #R27.
  
  
• 1997
  • (with J.-P. Allouche, E. Cateland, W. J. Gilbert, H.-O. Peitgen, 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.
  • (with J. M. Robson and C. Pomerance) Automaticity II: Descriptional complexity in the unary case. Appeared in Theoret. Comput. Sci. 180 (1997), 181-201.
  
  
• 1996
  • (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. van der Poorten) Convergents of folded continued fractions. Appeared in Acta Arithmetica 77 (1996), 77-96.
  • (with S. Lehr and J. Tromp) On the vector space of the automatic reals. Appeared in Theoret. Comput. Sci. 163 (1996), 193-210.
  • (with Y. Breitbart) Automaticity I: Properties of a measure of descriptional complexity. Appeared in 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.
  • (with Ian Glaister) A lower bound technique for the size of nondeterministic finite automata. Appeared in Information Processing Letters 59 (1996), 75-77.
  
  
• 1995
  • (with F. Morain and H. C. Williams) Discovery of a lost factoring machine. Appeared in Math. Intelligencer 17 (3) (Summer 1995), 41-47.
  • (with J. Tromp) Subword complexity of the generalized Thue-Morse word. Appeared in Information Processing Letters 54 (1995), 313-316.
  • Allouche, J.-P., Cateland, E., Peitgen, H.-O., Skordev, G., Shallit, J., 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
  • 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
  • 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, appeared in Mathematics of Computation 61 (1993), 351-354.
  • On the maximum number of distinct factors in a binary string, Graphs and Combinatorics 9 (1993), 197-200.
  
  
• 1992
  • 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.] Erratum: in the published version, at the top of page 191, line 4, in the definition of g(X) replace b(∞, n) with b(∞, 2n).
    Erratum: 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
  • 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.
  
  
• 1989
  • E. Bach and J. Shallit, Factoring with cyclotomic polynomials, Math. Comp. 52 (1989), 201-219.
  • Infinite products associated with counting blocks in binary strings, J. London Math. Soc., 39 (1989), 193-204.
  
  
• 1988
  • A generalization of automatic sequences, Theoret. Comput. Sci. 61 (1988), 1-16.
  • Fractals, bitmaps, and APL, APL Quote Quad 18 (3), 24-32.
  
  
• 1987
  • (with J.-P. Allouche, H. Cohen, and M. Mendès France) De nouveaux curieux produits infinis, Acta Arithmetica 49 (1987), 141-153.
  
  
• 1986
  • Metric theory of Pierce expansions, Fibonacci Quart. 24 (1986), 22-40.
  • 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
  • (with Adi Shamir), Number-theoretic functions which are equivalent to number of divisors, appeared in Info. Proc. Letters 20 (1985), 151-153.
  • 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, appeared in Fibonacci Quarterly 22 (1984), 332-335.
  • 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.
  • Merrily we roll along: some aspects of ?", in APL 83 Conference Proceedings, pp. 243-249.
  
  
• 1982
  • 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.
  • Simple continued fractions for some irrational numbers, appeared in 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.

• 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.

• 1975
  • A simple proof that phi is irrational, appeared in Fibonacci Quarterly 13 (1975), 32. My first published paper. I include this bit of juvenalia just for completeness.

E-mail: