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)
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 Σ
^{1}
and Σ
^{2}
)
Lecture 6f (FO
^{2}
, Δ
_{2}
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)