• About these notes ...

• Lecture 1 (Regular Languages and Monoids)

• Lecture 1a (Monoids: An Example and an Application)

• Lecture 2 (Languages via Logical Formulae)

• Lecture 2a (First-order Logic over Words)

• Lecture 3 (MSO to Regular Languages)

• Lecture 4 (EF Games and First-order Definability)

• Lecture 5 (Schutzenberger's Theorem)

• LTL and its Expressive Completeness (Slides)

• Bounded Synchronization Delay and Aperiodicity (Handwritten Notes)

• Lecture 6 (Alternating Automata)

• Lecture 6a (Alternating Automata: direct arguments and a different formulation)

• Lecture 6b (LTL to Very Weak Alternating Automata to Aperiodic Monoids): Coming Soon!

• Lecture 6c (Green's Relations)

• Lecture 6d (Using Green's Relations: Schutzenberger's Theorem and Factorization Forest Theorem)

• Lecture 6e (Ordered Monoids and languages in Σ¹ and Σ²)

• Lecture 6f (FO ², Δ₂ and DA) [Partial. Rest coming soon!]

• Lecture 7 (Buchi Automata)

• Lecture 8 (Determinizing Buchi Automata)

• Lecture 9 (Buchi Games over Infinite Graphs)

• Lecture 10 (Complementation via Alternating Automata)

• Lecture 11 (Safra's Determinization Construction)

• Lecture 12 (Optimality of Safra's Construction and the Kupferman-Vardi Construction)

• Lecture 13 (From Streett Automata to Rabin Automata and Back)