Mikołaj Bojańczyk

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:

- version of May 8. If you find mistakes, add them to this page. You will get points!
- version of April 15. If you find mistakes, add them to this page. You will get points!
- version of April 1. If you find mistakes, add them to this page. You will get points!
- version of March 17
- version of March 6

A plan of the lectures (updated periodically):

- finite semigroups and the languages that they recognise
- Green’s relations
- factorisation forests
- first-order logic, LTL, and aperiodic monoids
- infix trivial monoids and zigzags
- determinisation of Büchi automata
- mso ⊆ recognisability for ◦-words
- finite representaiton of ◦-semigroups
- recognisability ⊆ mso for ◦-words
- monads (slides)
- syntactic algebras for monads (slides)
- forest algebra
- algebra for graphs of bounded treewidth (slides)
- recognisability = mso for graphs of bounded treewidth (slides 1)