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 (this has not materialised, I’m sorry).

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


The exam is oral. Here are the topic and some materials for them.

  1. Monoids and Green’s relations 
  2. Factorisation forests
  3. First-order logic and LTL
  4. Omega and scattered words
  5. Countable words
  6. Monads
  7. What is an algebra for graphs and Courcelle’s Theorem (also sections 3 and 4  here)
  8. Recognisability implies definability for bounded treewidth (these and these slides, also this paper if you reallly must)

Please email me to choose a time.  Choose any subset of the 8 topics in the list above, here is the exchange rate:
• 3 topics: dostateczny
• 4 topics: dobry
• 6 topics: bardzo dobry