Information for

Jeffrey Shallit


Jeffrey ShallitResearch interests

Professor Shallit is interested in the interplay between number theory, algebra, logic, discrete mathematics and the theory of computation. Most of his recent work focuses on combinatorics on words and automata theory, especially on decision procedures.

Combinatorics on words is the study of properties of strings of symbols. A common theme is avoidability properties, such as, does there exist an infinite string on three symbols that avoids squares, that is, all subwords of the form xx, where x is a string?

Automata theory studies the properties of simple models of computation. There one of the themes is state complexity: the smallest number of states required to accept certain languages.

Another one of his interests is algorithmic number theory (the design and analysis of integer factorization and primality testing).

Finally, Professor Shallit has also written on subjects as diverse as computer graphics, history of mathematics and computer science, and science versus pseudoscience.

Degrees and awards

AB Math (Princeton), PhD (California, Berkeley)

Marsland Faculty Fellow (2010-2013); ACM Distinguished Scientist (2008); Outstanding Performance Award, University of Waterloo (2006, 2014); Faculty of Mathematics Fellow, University of Waterloo (2004-2006)

Industrial and sabbatical experience

Professor Shallit spent his most recent sabbatical (2009-2010) at MIT, where he worked on several book projects.

Representative publications

J. Borwein, A. van der Poorten, J. Shallit, and W. Zudilin, Neverending Fractions, Cambridge University Press, 2014.

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.

Luke Schaeffer and Jeffrey Shallit, The critical exponent is computable for automatic sequences, Int. J. Found. Comput. Sci. 23 (2012), 1611-1626.

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

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

E. Bach and J. Shallit. Algorithmic Number Theory, Vol. 1, Efficient Algorithms, MIT Press, 1996.

University of Waterloo
Contact information: