This one of the courses at the Lipa Summer School.

#### Mikołaj Bojańczyk

*What is a recognisable language?*

Videos: 1, 2, 3, 4

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.