CS 860: Automatic Sequences

University of Waterloo: Winter 2020

Time: Meets Tuesday and Thursday, 1:00 PM - 2:20 PM in DC 2568



Jeffrey Shallit, DC 3134, x 34804, shallit at uwaterloo.ca. Office hours: 2:30 - 3:20 PM Wednesdays, or by appointment, or when office door is open. If office door is closed, please don't knock!

Keeping in touch

We will use Piazza for course announcements.


There is a textbook for the course, the book Automatic Sequences, by Allouche and Shallit, which will give you some idea of what we will cover. It will be available from the University bookstore.

Errata for the course textbook can be found here. If you find a new, previously unreported error, report it to the instructor to get a bonus point in your course mark (subject to approval).

Course Description

Automatic sequences are sequences that lie in between the most ordered sequences (ultimately periodic sequences) and the least ordered sequences (random sequences). They are simple in many ways; yet surprisingly subtle in their properties. In this course, you will see definitions and examples of these sequences, and the many places they occur in mathematics and computer science. The relationship between automatic sequences and other areas of mathematics, including combinatorics, algebra, number theory, and logic, will be explored. Students will get to see many open problems, some of which are quite accessible. (Several published papers arose from previous versions of the course.) Some of the topics we will cover include:


General mathematical sophistication is the most important prerequisite. You should be very comfortable with formal mathematical proofs, especially proofs by induction. A knowledge of basic automata theory at the level of Waterloo's CS 360 or 365 would be helpful, but not essential. Knowledge of basic algebra (groups, rings, fields) at the level of Waterloo's PMATH 347/348 would be helpful, but not essential. Knowledge of basic combinatorics (generating functions, etc.) at the level of Waterloo's MATH 239/249 and CO 330 would be helpful, but not essential.


There will be 3 problem sets, with problems of varying difficulty. They are worth 50% of the course mark.

There will be a final course project. It will also be worth 50% of the course mark. This can be

  1. reading a paper or papers from the literature, writing a 5-15 page report on them, and presenting them in class in a 15-30 minute presentation; or
  2. working on an open research problem or problems, writing a 5-15 page report, and presenting your results in class in a 15-30 minute presentation; or
  3. writing or re-writing Wikipedia pages on various topics discussed in class (a list will be provided). This option is available for those who are a bit presentation-phobic.
Information about the course project is here. The important dates are: choose project by Thursday, February 6 2020, and hand in a 1-page sheet with your project and a selection of references then. Present project in class in the last three weeks; hand in written portion by last day of class. More details about the oral presentation, including how you will be evaluated, are here.

There will be no midterm or final.

Open problems

During the course, I will mention many interesting open problems. Solve any of them for bonus marks in the course.


A basic tool that everybody in the course should know about is the On-Line Encyclopedia of Integer Sequences, available at https://oeis.org. If you explore a sequence that does not appear there, please submit it. You can gain bonus points for submitting interesting sequences.

Tentative outline of the course


Problem Sets

Some papers relevant to the course

Some papers written by students in previous graduate courses similar to this one