Mikołaj Bojańczyk

Algebraic language theory (automaty a półgrupy)

This course is about an alternative approach to regular languages, where one uses monoids (and more fancy algebraic structures) instead of automata.  I use notes from this lecture, but I hope to create a new version in pdf for this one.

Lecture: Fridays 14:15-15:45 (room 4060)
Exercises: Fridays 16:00-17:30 (room 4060)

  1. Green’s relations
  2. First-order logic and LTL
  3. Factorisation forests
  4. MSO and \omega-words
  5. Monads
  6. Countably infinite words (2 lectures)
  7. Graphs
  8. MSO definability implies recognisability
  9. Recognisability implies MSO (3 lectures)
  10. An introduction to Tame Congruence Theory (2 lectures)


There will be an oral exam. The grade can be improved by doing special assignments, which will appear throughout the semester.