Infinite automata
General data
Course ID: | 1000-2M22AN |
Erasmus code / ISCED: |
11.3
|
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
|
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 hard decidability proof: reachability in Petri nets. We will also mention some interesting problems that still remain open. We will present topics chosen among: 1. Semilinear sets, properties and applications 2. Wqo techniques 3. Decision problems for 1-dimensional VASS 4. Lossy counter automata 5. Coverability and reachability in VASS 6. Reversible systems 7. Equivalences in infinite-state systems 8. Language equivalence of deterministic PDA 9. Separability in infinite-state systems 10. Automata with registers or clocks |
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: |
Star assignments and oral exam. In the case of PhD student an additional requirement: solving of some star assignment or presenting some recent research article on the chosen topic. |
Classes in period "Winter semester 2024/25" (future)
Time span: | 2024-10-01 - 2025-01-26 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Wojciech Czerwiński, Sławomir Lasota | |
Group instructors: | Wojciech Czerwiński, Sławomir Lasota | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Copyright by University of Warsaw.