lecture

tutorials

USOS

MOODLE

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.