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).**

- automatic sequences
- fixed points of morphisms
- relationship between automatic sequences and algebra over a finite field
- automatic real numbers
- frequency and entropy
- transcendence theory of real numbers
- Cobham's big theorem
- combinatorics on words
- relationship between automatic sequences and logic
- k-regular sequences and combinatorial enumeration

There will be a final course project. This can be

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

There will be no midterm or final.

Here is the problems list.

- Week 1: Introduction to automatic sequences. Course organization.
Base-
*k*representation. Automata (DFA, DFAO, NFA). Transducers. Examples of automatic sequences. The Thue-Morse sequence. The Rudin-Shapiro sequence. Finite-state functions. Robustness of the definition of automatic sequence. The Kolakoski sequence. - Week 2: Morphisms: uniform and non-uniform. The infinite
Fibonacci word. Cobham's little theorem. Example: the tower of Hanoi.
The
*k*-kernel. Closure properties of automatic sequences. - Week 3: Paperfolding and paperfolding sequences. Connection to continued fractions. Introduction to Christol's theorem.
- Week 4: Proof of Christol's theorem. Transcendence in finite characteristic. Transcendence of the finite field analogue of π. Sturmian and characteristic words.
- Week 5: the logical approach to automatic sequences. Synchronized
sequences. Using the
`Walnut`automatic theorem-proving software. - Week 6:
*k*-regular sequences. Examples and applications. Basic results. Using`Walnut`with k-regular sequences. - Week 7: automatic real numbers. Transcendence. Subword complexity. Automatic sets of rational numbers.
- Week 8: Cobham's big theorem. Applications. General (non-uniform) morphisms. Frequency of letters. Return words.
- Week 9: TBA
- Weeks 10-12: student presentations.

- Problem Set 1, distributed Sunday January 15;
due Tuesday January 31 in class.
- Solutions to Problem Set 1. You will need a username and password (given out in class).

- Problem Set 2, distributed Tuesday January 31; due Tuesday February 14 in class.

- What is an automatic sequence?, by Eric Rowland,
*Notices of the AMS***62**(2015), 274-276. - Number theory and formal languages, by Jeffrey Shallit, in
*Emerging Applications of Number Theory*, Vol. 109 of IMA Volumes in Mathematics and its Applications, pp. 547-570. - The
ubiquitous Prouhet-Thue-Morse sequence, by Jeffrey Shallit, in C.
Ding. T. Helleseth, and H. Niederreiter, eds.,
*Sequences and Their Applications: Proceedings of SETA '98*, Springer-Verlag, 1999, pp. 1-16. - Expansions of algebraic numbers, by Yann Bugeaud. Final version appeared in
*Four Faces of Number Theory*, European Mathematical Society, 2015, pp. 31-75.

- Soroosh Yazdani,
Multiplicative functions and
*k*-automatic sequences,*Journal de théorie des nombres de Bordeaux***13**(2001) 651-658. - Michael Forsyth, Amlesh Jayakumar, Jarkko Peltomäki, and
Jeffrey Shallit, Remarks on privileged words,
*Internat. J. Found. Comput. Sci.***27**(2016), 431-442. - Chen Fei Du, Jeffrey Shallit, and Arseny Shur,
Optimal bounds for the similarity density of the Thue-Morse word
with overlap-free and 7/3-power-free infinite binary words,
*Internat. J. Found. Comput. Sci.***26**(2015), 1147-1165. - E. Grant, J. Shallit, and T. Stoll,
Bounds for the discrete correlation of infinite sequences on
*k*symbols and generalized Rudin-Shapiro sequences.*Acta Arith.***140**(2009), 345-368. - Mathieu Guay-Paquet and Jeffrey Shallit,
Avoiding squares and overlaps over the natural numbers.
*Discrete Math.***309**(2009), 6245-6254. - Yu-Hin Au, Aaron Robertson, and Jeffrey Shallit,
van der Waerden's theorem and avoidability in words.
*Integers***11**(2011), Paper A7, 15 pp. - Yu-Hin Au, Generalized de Bruijn words for primitive words and powers,
*Discrete Math.***338**(2015), 2320-2331.