Announcements:
- [2020-10-12] We start only on Oct 19.
- [2020-10-17] MOODLE course created.
- [2020-11-16] The first series of star assignments added. Deadline 2020-12-15.
- [2020-11-23] Additional lecture notes uploaded.
- [2020-12-06] Lecture notes updated.
- [2020-12-16] The second series of star assignments added. Deadline 2021-01-15.
- [2020-12-27] Grading scores of the first series of star problems.
- [2021-01-24] The third series of star assignments added. Deadline 2021-02-07.
- [2021-01-24] Exam articles added. Proposed exam dates: 2021-02-08.
- [2021-01-25] The third series of star assignments corrected!
- [2021-01-27] Exam info updated.
- [2021-01-28] Grading scores of the second series of star problems.
Tentative plan:
- automata on omega-words [ blackboard notes ]
- determinisation of automata on omega-words [ blackboard notes ]
- Church's synthesis problem and infinite duration games [ blackboard notes ]
- memoryless determinacy of parity games [ blackboard notes ]
- the star height problem and distance automata [ blackboard notes ]
- regular languages = monadic second-order logic [ blackboard notes ]
- automata learning [ blackboard notes ]
- lossy counter machines [ blackboard notes ]
- timed automata [ blackboard notes ]
- timed automata/weighted automata [ blackboard notes ]
- weighted automata [ blackboard notes ]
- transducers I [ blackboard notes ]
- transducers II [ blackboard notes ]
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 2020-12-15)
- the second series (deadline 2021-01-15)
- the third series (deadline 2021-02-07)
- 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
- S. Lasota, I. Walukiewicz. Alternating timed automata
- J. Fearnley, M. Jurdziński, Reachability in two-clock timed automata is PSPACE-complete
- B. Berard, C. Duford, Timed Automata and Additive Clock Constraints
- W. Czerwiński, S. Lasota, R. Mayer, S. Muskalla, K.N. Kumar, P. Saivasan, Regular Separability of Well-Structured Transition Systems
- S. Schmitz, The Parametric Complexity of Lossy Counter Machines
- Ph. Schnoebelen, Lossy Counter Machines Decidability Cheat Sheet
Literature:
Most of the material is to be found in the book draft:- M. Bojańczyk, W.Czerwiński, An automata toolbox