Mikołaj Bojańczyk

2017/2018

- Green's relations
- First-order logic and LTL
- Factorisation forests
- MSO and \omega-words
- Monads
- Countably infinite words (2 lectures)
- Graphs
- MSO definability implies recognisability
- Recognisability implies MSO (3 lectures)
- An introduction to Tame Congruence Theory (2 lectures)

- version of November 2
- version of November 8
- version of November 13
- version of November 30
- version of February 2, 2018
- version of February 6, 2018

If you find a mistake (or something not clear, or something you can do better, etc.) in the notes, please put it here. Every mistake (for the first person to find it) increases your grade, with .02 for typos, .05 for small errors, and bigger values for bigger or more subtle mistakes.

- Determinisation of $\omega$-automata
- Infinite duration games • Parity games in quasipolynomial time
- Tree-walking automata
- Distance automata • Vector Addition Systems
- Weighted automata over a field
- Decidability of the first-order theory of (R,+,*) no notes for this!
- Polynomial grammars
- Parsing in matrix multiplication time • Learning automata

2016/2017

- automata on infinite words: determinisation
- games of infinite duration: the Büchi-Landweber theorem
- distance automata: decidability of limitedness
- treewidth and mso: Courcelle's theorem
- learning automata: the Angluin algorithm
- transducers

Here is an overview of the course

- Introduction to automata with registers
- Alternating automata with registers
- Data automata
- Logic on data words
- Reachability for vector addition systems

- Sets with atoms and orbit-finiteness
- Automata in sets with atoms
- Atoms with structure other than equality
- Oligomorphism
- What is a computable function?
- Turing machines with atoms

Lipa

- Stephan Kreutzer (Berlin)
*Algorithmic meta-theorems*(videos: 1, 2, 3, 4) - Joël Ouaknine (Saarbrücken)
*Decision Problems for Linear Recurrence Sequences*(videos: 1, 2, 3, 4) - Moshe Vardi (Rice)
*Linear-time verification and synthesis*(videos: 1, 2, 3, 4) - Mikołaj Bojańczyk (Warsaw, organiser)
*What is a recognisable language?*(videos: 1, 2, 3, 4)

~~May 30 Registration with request for student accommodation~~~~June 20 Registration without request for student accommodation~~~~July 3-6 School~~

The school is part of the grant

- Rajeev Alur (UPenn)
*Regular processing of data streams* - Matt Valeriote (McMaster)
*Finite algebras and connections with tree languages* - Igor Walukiewicz (Bordeaux)
*MSOL and higher-order computation* - Mikołaj Bojańczyk (Warsaw, organiser)
*Recognisable languages of graphs*

- May 15 End of registration with request for student accommodation
- June 15 End of registration without request for student accommodation
- July 25-29 School

The school is part of the grant

2015/2016

The general theme is monoids instead of automata. We will go deep (e.g. on the structure of finite monoids) and wide (on "monoids" for infinite words etc.)

**Lecture**: Thursday 12:15 – 13:45 (room 3170)
**Exercise**: Thursday 14:15 – 15:45 (room 3170)

I will use the notes from my previous course, but modified.

- automata on infinite words: determinisation
- games of infinite duration: the Büchi-Landweber theorem
- weighted automata: decidable and undecidable problems
- distance automata: decidability of limitedness
- tree-walking automata: failure of determinisation
- transducers
- learning automata: the Angluin algorithm
- automata with infinite alphabets
- sets with atoms

2014/2015

2013/2014

2011/2012

2009/2010

2008/2009