Algorithmics of Petri nets

General data

Course ID:	1000-2M20ALP
Erasmus code / ISCED:	11.303 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:	Algorithmics of Petri nets
Name in Polish:	Algorytmika sieci Petriego
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):	(not available) 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
Prerequisites (description):	Command of linear algebra in the areas of linear spaces and subspaces as well as solving sets of linear equations.
Mode:	Classroom
Short description:	The course focuses on one of the most fundamental computation models: Petri nets (and almost equivalent model of Vector Addition Systems with States - VASS) and their restrictions and extensions. I plan to present algorithmic constructions interesting from the mathematical point of view and lower complexity bounds. I will focus on the central problem of reachability, but it will not be the only topic considered. The main goal of the course is the presentation of current state of art in the area with emphasis on the most interesting constructions using original mathematical tools.
Full description:	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)
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.
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 methods and 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.

This course is not currently offered.

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