Announcements:
- [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.
- [2021-12-05] Lecture notes updated.
- [2021-11-29] Deadline for the first series of star assignments once more moved, to 2021-12-31.
- [2022-01-11] The first series of star assignments graded! Contact me in case of doubts.
- [2022-01-11] The second series of star assignments added. Deadline 2022-01-30.
- [2022-01-11] Exam articles added. Proposed exam dates: 2022-01-31.
- [2022-01-23] The last lecture will be online.
Tentative plan:
- automata on infite words [ tutorials problems ]
- determinisation of automata on infinite words [ tutorials problems ]
- infinite duration games and Church's synthesis problem [ tutorials problems ]
- memoryless determinacy of parity games [ tutorials problems ]
- the star height problem and distance automata [ tutorials problems ]
- automata and monadic second-order logic [ tutorials problems ]
- vector addition systems [ lecture whitoboard ] [ tutorials whiteboard ] [ tutorials problems ]
- lossy counter machines [ lecture whitoboard ] [ tutorials whiteboard ] [ tutorials problems ]
- timed automata [ lecture whitoboard ] [ tutorials whiteboard ] [ tutorials problems ]
- learning regular languages [ lecture whitoboard ] [ tutorials whiteboard ] [ tutorials problems ]
- transducers [ lecture whitoboard ]
- lecture cancelled [ tutorials problems ]
- weighted automata
- polynomial automata [ lecture whitoboard ]
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.- the first series (deadline 2021-12-31)
- the second series (deadline 2022-01-30)
- grading scores
Exam:
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:- C. Calude, S. Jain, B. Khoussainov, W. Li, F. Stephan, Deciding parity games in quasipolynomial time (plus Sect. 3 in An automata toolbox)
- Mikolaj Bojanczyk, Star Height via Games
- C. Rackoff, The Covering and Boundedness Problems for Vector Addition Systems
- S. Lasota, Improved Ackermannian lower bound for the Petri nets reachability problem
- A. Finkel, F. Schnoebelen, Well-structured transition systems everywhere!
- S. Schmitz, The Parametric Complexity of Lossy Counter Machines
- S. Lasota, I. Walukiewicz, Alternating timed automata
- J. Fearnley, M. Jurdziński, Reachability in two-clock timed automata is PSPACE-complete
- M. Benedikt, T. Duff, A. Sharad, J. Worrell, Polynomial automata: zeroness and applications (plus Sect. 11 in An automata toolbox)
Literature:
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.