University of Warsaw - Central Authentication System

QUICK START
STUDENTS AND STAFF
FACULTIES
COURSES
- Languages, automata and computations II
STUDIES
DORMITORIES
HELP

Languages, automata and computations II

General data

Course ID:	1000-2M15ZTA
Erasmus code / ISCED:	11.3 The subject classification code consists of three to five digits, where the first three represent the classification of the discipline according to the Discipline code list applicable to the Socrates/Erasmus program, the fourth (usually 0) - possible further specification of discipline information, the fifth - the degree of subject determined based on the year of study for which the subject is intended. / (0612) Database and network design and administration The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title:	Languages, automata and computations II
Name in Polish:	Języki, automaty i obliczenia II
Organizational unit:	Faculty of Mathematics, Informatics, and Mechanics
Course groups:	(in Polish) Grupa przedmiotów obieralnych dla informatyki magisterskiej- specjalność Automaty, logika, złożoność (in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Courses for PhD students in Computer Science Elective courses (facultative) for Computer Science Elective courses for Computer Science and Machine Learning
ECTS credit allocation (and other scores):	6.00 Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
Language:	English
Type of course:	elective monographs
Short description:	Automata over infinite words, trees, and other input structures. Non-standard control: probabilistic/weighted, lossy, concurrent, timed. Connections between automata, games and logics. Algorithmic (un)decidability of decision problems.
Full description:	• 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.
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.
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 methods and 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.

Classes in period "Winter semester 2024/25" (past)

Time span:	2024-10-01 - 2025-01-26	Selected timetable range: weekly course term Go to timetable MO CW TU W WYK TH CW FR
Type of class:	Classes, 30 hours more information Lecture, 30 hours more information
Coordinators:	Mikołaj Bojańczyk
Group instructors:	Mikołaj Bojańczyk, Lorenzo Clemente, Łukasz Kamiński
Students list:	(inaccessible to you)
Credit:	Examination
Notes:	(in Polish) Zajęcia w grupie 2 odbywają się po angielsku.

Classes in period "Winter semester 2025/26" (future)

Time span:	2025-10-01 - 2026-01-25	Selected timetable range: weekly course term Go to timetable MO TU CW W WYK TH CW FR
Type of class:	Classes, 30 hours more information Lecture, 30 hours more information
Coordinators:	Mikołaj Bojańczyk
Group instructors:	Mikołaj Bojańczyk, Łukasz Orlikowski, Michał Skrzypczak
Students list:	(inaccessible to you)
Credit:	Course - Examination Lecture - Examination
Notes:	(in Polish) Zajęcia w grupie 2 odbywają się po angielsku.

Course descriptions are protected by copyright.
Copyright by University of Warsaw.