Lecture Summaries -- Winter 2017

These summaries will be added as the course takes place.

Week 1

Lecture 1: Wednesday, January 4, 2017:
Information about the course. Marking, exams, Piazza, etc. Course textbook. Course outline. Introduction to combinatorics on words (Chapter 2 of textbook). Basic operations on words: concatenation, reverse, power, perfect shuffle. Basic operations on languages: union, intersection, complement, concatenation. Proofs by induction. The Lyndon-Schutzenberger theorems.

Week 2

Lecture 2: Monday, January 9 2017:
The textbook is still not in the bookstore, but they are promising it soon. In the meantime, there is a copy of the textbook on reserve in the library. More on the Lyndon-Schutzenberger theorems; see the handout. Primitive words. The primitive words problem. I offer an automatic 100 for the course, and $200, for a solution. Introduction to the Fine-Wilf theorem (Theorem 2.3.5). Problem Set 1 is now available.

Lecture 3: Wednesday, January 11 2017:
The textbook is now available. We did Theorem 2.3.5 (the Fine-Wilf theorem). Conjugates. Bordered and unbordered words. Theorem 2.4.2. Theorem 2.4.3: a word is primitive if and only if it has an unbordered conjugate. Problem-solving in small groups, session 1.

Week 3

Lecture 4: Monday, January 16 2017:
Repetitions in words. Overlaps. Squares. The Thue-Morse sequence t. Definition. The sequence t avoids overlaps (we did the alternative proof here). Constructing an infinite word that avoids squares. Properties of the Thue-Morse sequence. (For more about the Thue-Morse sequence, you can read this survey paper or this recent column by James Propp.) Open problem: say something interesting about the lexicographically least squarefree word over the alphabet {0, 1, 2}.

Lecture 5: Wednesday, January 18 2017:
Finite automata and regular languages. Quotient, morphisms, substitutions. Closure of regular languages under these operations. Problem-solving in small groups, session2.