lecture

tutorials

USOS

MOODLE

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

Exam dates

Literature:

Most of the material is to be found in the book draft:

• M. Bojańczyk, W.Czerwiński, An automata toolbox

The remaining topic are treaded in these draft lecture notes.