# Jeffrey O. Shallit

**University of Waterloo - Canada**

**November 2011**

## Distinguished Lecture Colloquium

**50 Years of Fine and Wilf**

It is now almost 50 years since the classic paper of Nathan Fine and Herb Wilf entitled “Uniqueness theorems for periodic functions”. That paper - their only joint one - led to many other interesting results in combinatorics on words and other areas. In this talk I will give a new proof of the Fine-Wilf theorem and discuss some of the progress in the last 50 years.

## TUCS Short Course

**Automatic sequences, decidability, and enumeration**

A sequence $(a_n)_{n \geq 0}$ is said to be $k$-automatic if it can be generated by a finite automaton with output mapping $f$ as follows: the automaton accepts as input the base-$k$ expansion of $n$, in processing the input, it ends up in a state $p$, and $f(p) = a_n$. The class of automatic sequences includes such important examples as the Thue-Morse and Rudin-Shapiro sequences. Many interesting questions about such sequences are mechanically decidable. This includes, for example, whether the sequence contains repetitions of order $r$ ( “r'th powers”), whether the sequence is recurrent (every factor occurs infinitely often), etc. Furthermore, we can also mechanically enumerate related sequences, such as the number of distinct factors of length n.

**References**

- Jean-Paul Allouche and Jeffrey Shallit,
*Automatic Sequences*, Cambridge University Press, 2003. - J.-P. Allouche, N. Rampersad, and J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence,
*Theoret. Comput. Sci.***410**(2009), 2795--2803. - E. Charlier, N. Rampersad, and J. Shallit, Enumeration and decidable properties of automatic sequences, to appear, DLT 2011. Available at http://arxiv.org/abs/1102.3698.
- J. Shallit, The critical exponent is computable for automatic sequences, to appear, WORDS 2011. Available at http://arxiv.org/abs/1104.2303