These summaries will be added as the course takes place.

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.

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.

Repetitions in words. Overlaps. Squares. The Thue-Morse sequence

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, session 2.

Inverse morphism. Application to the (general) shuffle product. Theorem 3.3.9: closure of regular languages under inverse morphism. Transducers. Applications of transducers. Formal definition. Problem Set 3 is now available on the course home page.

Lecture 7: Wednesday, January 25 2017:

Finishing up the proof of Nivat's theorem. Nondeterministic versus
deterministic transducers. The
Kolakoski sequence problem.
Problem solving in groups, session 3.

Advanced closure properties of regular languages. Theorem 3.4.3: closure of regular languages under cycle (conjugate). Please read Theorem 3.4.1 and its proof if you haven't seen it before. The transformation automaton. Introduction to use of Boolean matrices. Problem Set 4 now available on course home page.

Lecture 9: Wednesday, February 1 2017:

More on Boolean matrices. Introduction to the Myhill-Nerode theorem.
Problem solving in small groups, session 4.
Grad students enrolled in 662
should have turned in their project info by now.

More about the Myhill-Nerode theorem. Proof. Examples. Application: there exist NFA's of

Lecture 11: Wednesday, February 8 2017:

The Lyngsø-Pedersen conjecture
(Open Problem 27).
Minimization algorithms for DFA's and applications.
Group problem solving, session 5.

Improving the naive algorithm for DFA minimization. Applications.

Lecture 13: Wednesday, February 15 2017:

The subsequence and subword orderings. Antichains (sets of pairwise
incomparable elements). The subsequence ordering has no infinite
antichains. Minimal elements. The set of minimal elements of a language
is finite. Regularity of sup(L) and sub(L).
Group problem solving, session 6.

Context-free languages.