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

The lecture is on Tuesdays, 12:15 in room 5820. The exercises are on Wednesdays, 16:15 in room 5820, with Wojciech Czerwiński. Here is a plan of the lecture. There was a similar lecture last year and the year before that. This year we use lecture notes in pdf (some topics in the notes will not be covered by the lecture, and will not be on the exam). Here is the current version:

• 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.

Exam. The exam is an oral exam, which is mainly questions about the proofs of theorems. Please email me to choose a time, or better use this spreadsheet .You can improve your exam grade using the star exercises.  Choose any subset of the 8 topics in the list below, here is the exchange rate:

• 2 topics: dostateczny
• 3 topics: dobry
• 4 topics: bardzo dobry

1. Determinisation of -automata
2. Infinite duration games • Parity games in quasipolynomial time
3. Tree-walking automata
4. Distance automata • Vector Addition Systems
5. Weighted automata over a field
6. Decidability of the first-order theory of (R,+,*) no notes for this!
7. Polynomial grammars
8. Parsing in matrix multiplication time • Learning automata