Mikołaj Bojańczyk

This lecture is a choice of slightly more advanced topics from automata theory.

The lecture is on Tuesdays, 12:15 in room 5070. The exercises are on Wednesdays, 16:15 in in room 5820, with Wojciech Czerwiński.

  1. automata on infinite words: determinisation
  2. games of infinite duration: the Büchi-Landweber theorem
  3. weighted automata: decidable and undecidable problems
  4. distance automata: decidability of limitedness
  5. tree-walking automata: failure of determinisation
  6. transducers
  7. learning automata: the Angluin algorithm
  8. automata with infinite alphabets
  9. sets with atoms

Here are the star exercises and their solvers.

Exam. The exam is an oral exam. Please email me to choose a time or use this link for Feb 15. Choose any subset of the 9 topics in the list above, here is the exchange rate:
• 3 topics: dostateczny
• 5 topics: dobry
• 7 topics: bardzo dobry



Leave a Reply

Your email address will not be published.