This one of the courses at the Lipa Summer School.
This course is about the algebraic approach to regular languages, which uses algebras instead of automata. The emphasis is on the connection of recognisability and definability in monadic second-order logic MSO.
Click the title links for slides.
Part 1: finite words
Classical results from the algebraic approach to finite words, where the algebras are monoids. As one example of the usefulness of monoids, I will present the Factorisation Forest Theorem of Imre Simon.
Part 2: infinite words
Monoids for infinite words, such as countable labelled linear orders.
Part 3: monads
A bit of abstract nonsense, trying to answer the question: what is an algebra in general? The answer is to use Eilenberg-Moore algebras over a suitably chosen monad.
Part 4: graphs
Graphs. I will give half of the proof of the following result: for a class of graphs of bounded treewidth, being recognisable is equivalent to being definable in monadic second-order logic.