Fundamentals of Computing and Discrete Mathematics

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
  1. Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge University Press, 2003.
  2. J.-P. Allouche, N. Rampersad, and J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence, Theoret. Comput. Sci. 410 (2009), 2795--2803.
  3. 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.
  4. J. Shallit, The critical exponent is computable for automatic sequences, to appear, WORDS 2011. Available at http://arxiv.org/abs/1104.2303
Last modified: