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 August 26. If you find mistakes, add them to this page. You will get points!
• version of July 31. If you find mistakes, add them to this page. You will get points!
• version of June 25. If you find mistakes, add them to this page. You will get points!
• version of June 16. If you find mistakes, add them to this page. You will get points!
• version of June 5. If you find mistakes, add them to this page. You will get points!
• 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):

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)
15. 14 continued, same slides