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)

Exam

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