Selected papers 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.

• 2009
  • 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", preprint, January 2009.
  • 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", to appear Information and Computation.
  • (with N. Rampersad, N. Santean, and B. Ravikumar), "State complexity of unique rational operations", Theoret. Comput. Sci. 410 (2009), 2431-2441. DOI link

• 2008
  • (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. To appear, Acta Arithmetica.
  • 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.-Y. Kao, Andrew Malton, and Narad Rampersad), "On NFAs where all states are final, initial, or both", submitted.
  • (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. To appear, special issue of Theoret. Comput. Sci..
  • (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.

• 2005
  • (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.
  • (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
  • The mathematics of Per Nørgård's rhythmic infinity system (to appear, Fibonacci Quarterly)
  • (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. postscript 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..
    • postscript
    • 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.
  • (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
  • (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.
  • (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.
  
  
• 1994
  • (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 postscript format
    • In pdf format
  • The "3x+1" problem and finite automata, Bulletin of the EATCS, No. 46 (February 1992), 182-185.
  • 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.]
  • 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
  • (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.
  
  
• 1989
  • Infinite products associated with counting blocks in binary strings, J. London Math. Soc., 39 (1989), 193-204.
  
  
• 1987
  • (with J.-P. Allouche, H. Cohen, and M. Mendès France) De nouveaux curieux produits infinis, Acta Arithmetica 49 (1987), 141-153.
  
  
• 1986
  • Sums of divisors, perfect numbers, and factoring, SIAM J. Comput. 15 (1986), 1143-1154.
  
  
• 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.
  
  
• 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.

• 1979
  • Simple continued fractions for some irrational numbers, appeared in Journal of Number Theory 11 (1979), 209-217.

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

  ---

  E-mail: