Mikołaj Bojańczyk

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 summer school (Warsaw, July 3-6, 2017)

In general, the decidability of such problems is open, but various partial results are known. I will introduce some of the key mathematical tools for attacking these problems, and present some of the known results.

Lipa

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