Algorithmics of Petri nets 1000-2M20ALP
The course will consist of the selection of the following topics, number of lecture is approximated. Maybe the course will be enriched by some new, interesting results.
1. One counter automata – reachability and universality problems (2-3 lectures)
2. Boundedness and coverability problems for VASSes (2 lectures)
3. Steinitz Lemma and Z-VASSes (1 lecture)
4. Semilinear sets and two-dimensional VASSes (2 lectures)
5. Decidability of the reachability problem in VASSes (2 lectures)
6. Low-dimensional VASSes (2 lectures)
7. ExpSpace-hardness and Tower-hardness of the reachability problem (2 lectures)
8. Automata with one counter and pushdown (1 lecture)
9. Brachning VASSes (1 lecture)
10. Separability problem in subclasses of VASSes (2 lectures)
Type of course
Mode
Prerequisites (description)
Learning outcomes
Students learn techniques for design and analysis of asynchronous concurrent systems. They are able to use mathematical methods to analyze systems (K_W02, K_U01). They acquire knowledge about the complexity of reachability problems in Petri nets, including their combinatorial diversity.
Assessment criteria
Depending on the number of students: either oral or writing final exam. During the course star exercises will be provided, solving them can positively influence the final grade. This year we will have oral exam, questions will concern mainly theoretical topics presented at the lecture.
Bibliography
- J. Esparza: Decidability and Complexity of Petri Net Problems - An Introduction.1996
- M. Blondin, A. Finkel, S. Goller, C. Haase, P. McKenzie, Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete, 2014
- J. Leroux, G. Sutre, P. Totzke, On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension, 2015
- other recent scientific papers concerning contemporary achievements in the study of Petri nets.
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: