Lecture: Concurrency Theory
Sommer 2024
News
- 25. März
- Die Informationen auf dieser Seite sind noch vorläufig.
Organisation
- Die Vorlesung wird von Prof. Dr. Roland Meyer gehalten.
- Die Übung wird von Jan Grünke betreut.
-
Die Termine der Veranstaltung sind
- Vorlesung: Montag und Dienstag 16:45-18:15 Uhr (IZ 358).
- Übung: Mittwoch 13:15-14:45 Uhr (IZ 358).
- Die Vorlesung startet am 08.04.2024.
- Die Übung startet am 10.04.2024.
- Falls Sie die Vorlesung in den Bachelor einbringen möchten, klären Sie dies bitte mit dem Prüfungsamt ab.
Modul
Es handelt sich um eine (4+2) Veranstaltung. Um das Modul erfolgreich abzuschließen, sind zwei Leistungen zu erbringen:
- Prüfungsleistung: Zu erbringen durch Bestehen einer mündlichen Abschlussprüfung zu Beginn des vorlesungsfreien Zeitraums. Das genaue Prüfungsdatum wird zeitnah bekannt gegeben.
- Studienleistung: Zu erbringen durch das erfolgreiche Bearbeiten von mindestens 40% der Übungsaufgaben. Es wird alle 2 Wochen ein Übungsblatt geben.
Prüfung
TBDVorlesungsnotizen
Die Vorlesung hat als Ziel folgendes Resultat und die zugrunde liegenden Techniken zu verstehen. On the Separability Problem of VASS Reachability LanguagesEs gibt Material von vergangenen Semestern. Allerdings enthält diese Vorlesung auch neue Themen, die nur in den handschriftlichen Notizen zu finden sind.
Handschriftliche Notizen:
- Woche 1: Überblick, Regular Separability, Petri Nets/VASS, PN invariants, Kirchhoff Equations, Z-VASS Reachability
- Woche 2: Coverability Graphs, Well quasi orderings, Characterization of Z-VASS Reachability
- Woche 3: MGTS, Characterization of Z-Reachability in MGTS, Perfectness, Lambert's Iteration Lemma
Übungsblätter
Die Übungsblätter werden während des Semesters hier zur Verfügung gestellt.
Literature
Die Vorlesungen werden sich auf die folgenden Bücher und Artikel stützen. Die meisten von ihnen sind online verfügbar, die übrigen können in der Bibliothek gefunden werden.- L. Priese and H. Wimmel: Petri-Netze. Springer, 2003.
- W. Reisig. Petri nets: An Introduction. Monographs in Theoretical Computer Science - An EATCS Series, Springer, 1985.
- P. H. Starke: Analyse von Petri-Netz-Modellen: Leitfäden und Monographien der Informatik, Teubner, 1990.
- J. Esparza and S. Melzer: Verification of Safety Properties Using Integer Programming: Beyond the State Equation. Formal Methods in System Design, 2000. [PDF]
- J. Esparza: Decidability and complexity of Petri net problems – an introduction: Lectures on Petri Nets I: Basic Models. Springer, 1998. [PDF]
- J. Esparza and M. Nielsen: Decibility issues for Petri nets-a survey. Journal of Information Processing and Cybernetics EIK, 30(3):143-160, 1994. [PDF]
- J. Esparza and K. Heljanko: Unfoldings. Monographs in Theoretical Computer Science - An EATCS Series, Springer, 2008. [PDF]
- C. Rackoff: The covering and boundedness problems for vector addition systems. Theoretical Computer Science, Volume 6, issue 2, 1978. [Link]
- C. Dufourd et al: Reset nets between decidability and undecidability. Automata, Languages and Programming, 1998. [PDF]
- P. Jančar: Undecidability of bisimilarity for Petri nets and some related problems. Theoretical Computer Science, Volume 148, issue 2, 1995.
- P. Jančar, J. Esparza, and F. Moller: Petri nets and regular processes. Journal of Computer and System Sciences, Volume 59, issue 3, 1999.