Mikołaj Bojańczyk

This one of the courses at the Lipa Summer School.

Mikołaj Bojańczyk

What is a recognisable language?

Videos: 1234

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.