University of Warsaw - Central Authentication System

Infinite automata

General data

Course ID:	1000-2M22AN
Erasmus code / ISCED:	11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title:	Infinite automata
Name in Polish:	Automaty nieskończone
Organizational unit:	Faculty of Mathematics, Informatics, and Mechanics
Course groups:	(in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Elective courses for Computer Science
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
Main fields of studies for MISMaP:	computer science
Type of course:	elective monographs
Requirements:	Languages, automata and computations 1000-214bJAO
Prerequisites:	Computational complexity 1000-218bZO
Short description:	Algorithmic analysis of automata with infinitely many states: pushdown automata, Petri nets, automata over an infinite alphabet.
Full description:	Infinite state-spaces are ubiquitous in computer science, for instance they arise as a consequence of unbounded stack depth or unbounded concurrency. It is sometimes arguably better to consider an infinite set of states, instead of artificially restricting to an a priori finite but astronomically large finite set. This is the case, for instance, in pushdown automata, register automata, timed automata or Petri nets. Despite the infinity of state spaces, many important decision problems are algorithmically solvable for these models. We will investigate the most interesting of these problems, in particular two hard decidability proofs: reachability in Petri nets and equivalence of deterministic pushdown automata. We will also mention some interesting problems that still remain open.
Bibliography:	J. Fearnley, M. Jurdziński, Reachability in two-clock timed automata is PSPACE-complete, ICALP 2013. Petr Jancar, Bisimulation Equivalence of 1st Order Grammars, ICALP 2014. Roadmap of infinite results, http://www.brics.dk/~srba/roadmap/roadmap.pdf S. Lasota, I. Walukiewicz, Alternating Timed Automata. ACM Transactions on Computational Logic 9(2), 2008. W. Czerwiński, Ł. Orlikowski, Reachability in Vector Addition Systems is Ackermann-complete, FOCS 2021. S.Lasota, VASS reachability in three steps, 2020. Jan A. Bergstra, Alban Ponse, and Scott A. Smolka, ed., Handbook of Process Algebra, Elsevier, 2001. W. Czerwinski, S. Lasota, R. Meyer, S. Muskalla, K. N. Kumar, P. Saivasan: Regular Separability of Well-Structured Transition Systems. CONCUR 2018
Learning outcomes:	(in Polish) Wiedza Student pogłębia wiedzę o klasycznych zastosowaniach teorii automatów. Umiejętności Student umie rozpoznać granice obliczalności różnych wariantów modeli. Student potrafi modelować różne problemy za pomocą odpowiednich automatów. Kompetencje Student rozumie narzędzia matematyczne wypracowane we współczesnej teorii automatów i potrafi z nich korzystać zarówno w samej informatyce, jak i w jej zastosowaniach
Assessment methods and assessment criteria:	(in Polish) Zadania gwiazdkowe i egzamin ustny. W przypadku zaliczania przedmiotu przez doktoranta, dodatkowym elementem zaliczenia będzie rozwiązanie przynajmniej jednego zadania z gwiazdką bądź zapoznanie się z oryginalnym, będącym blisko aktualnego frontu badań, artykułem naukowym i rozmowa z wykładowcą na temat tego artykułu.

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

Time span:	2024-10-01 - 2025-01-26	Selected timetable range: weekly course term Navigate to timetable
Type of class:	Classes, 30 hours more information Lecture, 30 hours more information
Coordinators:	Wojciech Czerwiński, Sławomir Lasota
Group instructors:	Wojciech Czerwiński, Sławomir Lasota
Students list:	(inaccessible to you)
Examination:	Examination

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