• [2021-10-01] This webpage launched.
  • [2021-10-11] Tutorials 1,2 added. Consecutive ones will be added gradually.
  • [2021-11-14] The first series of star assignments added. Deadline 2021-12-19.
  • [2021-11-20] We swtich to online mode - moodle course added.
  • [2021-11-29] Deadline for the first series of star assignments moved to 2021-12-22. Please submit your solutions via moodle

Tentative plan:

  • automata on infite words    [ tutorials ]
  • determinisation of automata on infinite words    [ tutorials ]
  • infinite duration games and Church's synthesis problem    [ tutorials ]
  • memoryless determinacy of parity games    [ tutorials ]
  • the star height problem and distance automata    [ tutorials ]
  • automata and monadic second-order logic    [ tutorials ]
  • vector addition systems    [ lecture whitoboard ] [ tutorials whiteboard ]
  • lossy counter machines    [ lecture whitoboard ]
  • timed automata   
  • first-order theory of reals   
  • weighted automata   
  • polynomial automata   
  • transducers   
  • learning regular languages   

Star assignments (zadania z gwiazdką):

Each assignment is worth 1 point, to be split equally over all students who correctly solve it. The total number of points gained by a student is added up to her/his exam grade, thus yielding the final grade.


An oral exam, based on the course material and/or on an article read by a student. The students will be able to choose an article out of the following set of articles:
  • t.b.a.


Most of the material is to be found in the book draft by M. Bojańczyk and W.Czerwiński, An automata toolbox. The remaining topic are treaded in these draft lecture notes.