Theoretical Computer Science

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

Vorlesungsnotizen

Es gibt Material von vergangenen Semestern. Allerdings enthält diese Vorlesung auch neue Themen, die nur in den handschriftlichen Notizen zu finden sind.

• Concurrency Theory, Vorlesungsnotizen 2011
• Concurrency Theory, Vorlesungsnotizen 2017

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
• Woche 4: Chapter 6: WSTS + Abdulla's Backwards search, Chapter 9: Expand, Enlarge & Check, Rackoff's bound for coverability,
• Woche 5: Lipton's hardness result part 1, Lipton's hardness result part 2
• Woche 6: MGTS Decomposition, Regular Separability of VASS reachability languages, Transducer Trick
• Woche 7: DMGTS, Deciding Regular Separability
• Woche 8: Separability Transfer, Inseparability
• Woche 9: DMGTS Decomposition part 1, DMGTS Decomposition part 2

Übungsblätter

Die Übungsblätter werden während des Semesters hier zur Verfügung gestellt.

• Blatt 1
• Blatt 2
• Blatt 3
• Blatt 4

Literature

• 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.