This course is about an alternative approach to regular languages, where one uses monoids or semigroups instead of automata.

Lecture: Tuesdays 8:45-10:15 (room 5070)
Exercises: Tuesdays 10:25-11:55 (room 5070)

Exam

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

Plan of the course

Finite words

• Recognising languages using monoids instead of automata
• Green’s relations
• First-order logic equals aperiodic monoids
• The factorisation forest theorem
• Piecewise testable languages

Infinite words

• Automata for ω-words
• Algebra for ω-words
• An interlude: monads
• Scattered infinite words
• All countable linear orders

Profinite words

• Profinite words