Mikołaj Bojańczyk

Algebraic language theory 2020


This course is about an alternative approach to regular languages, where one uses semigroups and monoids (and more fancy algebraic structures) instead of automata.

  • Lecture: Tuesdays 14:15-15:45 (room 3130)
  • Exercises: (given by Nathan Lhote) Tuesdays 16:00-17:30 (room 3130)

I use online notes from this lecture, but I will be updating them into a pdf version:

A plan of the lectures (updated periodically):

  1. finite semigroups and the languages that they recognise
  2. Green’s relations
  3. factorisation forests
  4. first-order logic, LTL, and aperiodic monoids
  5. infix trivial monoids and zigzags
  6. determinisation of Büchi automata
  7. mso ⊆ recognisability for ◦-words
  8. finite representaiton of ◦-semigroups
  9. recognisability ⊆ mso for ◦-words
  10. monads (slides)
  11. syntactic algebras for monads (slides)
  12. forest algebra
  13. algebra for graphs of bounded treewidth (slides)
  14. recognisability = mso for graphs of bounded treewidth (slides 1)