Languages, automata and computations II 1000-2M15ZTA
• Automata on infinite words, determinisation algorithm.
• Infinite duration games, finite-memory determinacy.
• Distance automata and star-height of regular expressions.
• Automata on finite and infinite trees.
• Decidability of monadic second-order logic on infinite trees.
• Algorithms of graphs of bounded tree-width.
• Automata modelling concurrency: Petri nets.
• Lossy machines: decidability using well quasi orders.
• Automata for real time: timed automata.
• Weighted/probabilistic automata: decidability of equivalence.
• Polynomial automata: decidability of equivalence using Hilbert's basis theorem.
• Learning algorithm for finite automata.
• Functions computable by finite automata.
• Examples of very simple undecidable problems. Turing degrees.
Type of course
Course coordinators
Learning outcomes
The student acquires a deeper knowledge of classical questions on computability and learns several active branches of advanced automata theory.
The student can switch between different representations of regular languages, with an understanding of the computational cost.
The student can model basic properties of computer systems, using automata of an appropriate type.
The student can identify undecidable problems, and construct suitable reductions.
The student understands mathematical tools present in modern automata theory and can use them both in computer science and its applications.
Assessment criteria
Oral exam. In addition, increasing of the final mark is possible due to solving star problems. Each problem is worth 1 divided by the number of students who correctly solved it.
For PhD students: obligatory participation in solving of star problems, or reading recent literature.
Bibliography
• M. Bojańczyk, W.Czerwiński, An automata toolbox, https://www.mimuw.edu.pl/~bojan/paper/automata-toolbox-book, 2018.
• J. E. Hopcroft, R. Motwani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, Warszawa 2005.
• Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.
Notes
|
Term 2024Z:
None |
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: