Concurrency Theory

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Concurrency Theory

Lehrveranstaltung mit SWS 2/2/0 (Vorlesung/Übung/Praktikum) in SS 2024

Dozent

Umfang (SWS)

  • 2/2/0

Module

Leistungskontrolle

  • Mündliche Prüfung

Matrix-Kanal

Vorlesungsreihe


News

  • On July 31st and August 6th, I offer slots for your oral examinations. Please contact our secretary, Kati Domann, to get your date and time slot. If you're looking for a complex exam (with more than one examiner), these dates are generally not applicable since all examiners must be available. In that case, you must still request an examination date.

Course Description

Modern computer systems are often multi-threaded or even fully distributed over several machines and geographical locations. Instead of the well-known sequential computational models (e.g., Turing machines, λ-calculus, etc.), the key notion for describing concurrent computations is that of a process. In this course, we study several phenomena occurring in concurrent computations using process calculi, for which we will define and analyze their formal semantics. As one of the key aspects, we ask when two processes are considered to be equivalent. Subsequently, we give an (incomplete) list of topics we strive for throughout the course.

  • From sequential to parallel processes (LTS, CCS)
  • Bisimulation and Coinduction
  • From sequential to concurrent processes (Petri nets)
  • Mobile processes (the π-calculus)
  • Expressive power of process calculi
  • Data-Aware Processes

Contact

If you have questions regarding the course, feel free to ask in the matrix chat or via email to the teacher of the course.

Schedule and Location

The course is taught in two sessions per week, one on Tuesdays DS2 (9.20-10.50) and Wednesdays DS3 (11.10-12.40). All the sessions take place in APB E005. We're currently planning the course sessions as on-site events. If necessary, we can retract to an Online mode, probably using Zoom. Exercises are intertwined with the lecture.

Acknowledgments

The first part of the lecture is based on the exposition Introduction to Bisimulation and Coinduction by Davide Sangiorgi. The slides Davide provides were an inspiration for the lecture material. The slides titled Part II have previously been used in lectures on coinduction.
  • Aceto, L., Ingólfsdóttir, A., Larsen, K. G., & Srba, J. (2007). Reactive Systems. Cambridge University Press.
  • Sangiorgi, D., & Walker, D. (2003). The pi-calculus: a theory of mobile processes. Cambridge University Press.
  • Sangiorgi, D. (2012). Introduction to bisimulation and coinduction. Cambridge University Press.
  • Milner, R. (1980). A calculus of communicating systems. : Springer Berlin Heidelberg.
  • Milner, R. (1999). Communicating and mobile systems. : Cambridge University Press.
  • Davide Sangiorgi (2012). Advanced topics in bisimulation and coinduction. : Cambridge University Press.
 * especially chapter 3 on "Algorithmics of Bisimilarity" by Luca Aceto et al.
 
  • Reisig, W. (2013). Understanding Petri Nets. : Springer Berlin Heidelberg.

Veranstaltungskalender abonnieren (icalendar)

Vorlesung Introduction and Motivation: Labeled Transition Systems DS2, 9. April 2024 in APB E005 Datei
Vorlesung Towards Bisimilarity DS3, 10. April 2024 in APB E005 Datei
Vorlesung Semantics of Programming Languages DS2, 16. April 2024 in APB E005 Datei
Entfällt --- DS3, 17. April 2024 in APB E005
Vorlesung Direct Style Semantics DS2, 23. April 2024 in APB E005 Datei
Übung Bisimulation and Bisimilarity DS3, 24. April 2024 in APB E005 Datei
Übung Domains and Fixed Points DS2, 30. April 2024 in APB E005 Datei
Entfällt Labor Day DS3, 1. Mai 2024 in APB E005
Vorlesung Structural Operational Semantics DS2, 7. Mai 2024 in APB E005 Datei
Übung Domains and Fixed Points DS3, 8. Mai 2024 in APB E005 Datei
Vorlesung Algebraic Properties of Bisimilarity DS2, 14. Mai 2024 in APB E005
Übung Operational Semantics DS3, 15. Mai 2024 in APB E005 Datei
Entfällt Pentacost Week DS2, 21. Mai 2024 in APB E005
Entfällt Pentacost Week DS3, 22. Mai 2024 in APB E005
Vorlesung The Untold Story of Hennessy and Milner DS2, 28. Mai 2024 in APB E005 Datei
Übung The Calculus of Communicating Systems DS3, 29. Mai 2024 in APB E005 Datei
Vorlesung First Decidability Results for Petri Nets (Detour Lecture) DS2, 4. Juni 2024 in APB E005 Datei
Entfällt Dies Academicus DS3, 5. Juni 2024 in APB E005
Vorlesung Bisimilarity Algorithms for Finite State Systems DS2, 11. Juni 2024 in APB E005
Übung P-Completeness of Bisimilarity (1) DS3, 12. Juni 2024 in APB E005
Vorlesung P-Completeness of Bisimilarity (2) DS2, 18. Juni 2024 in APB E005
Entfällt no exercise DS3, 19. Juni 2024 in APB E005
Vorlesung Decidability of Bisimilarity for (Some) Infinite State Processes DS2, 25. Juni 2024 in APB E005
Übung Undecidability Results for Infinite State Processes (Petri nets) DS3, 26. Juni 2024 in APB E005
Vorlesung Further Undecidability of Petri Net Equivalences DS2, 2. Juli 2024 in APB E005
Übung Reductions to Petri Net Reachability DS3, 3. Juli 2024 in APB E005
Vorlesung Immerman und Szelepcsényi on Steroids DS2, 9. Juli 2024 in APB E005
Übung Inductive Counting with Petri Net Programs DS3, 10. Juli 2024 in APB E005
Vorlesung Bisimilarity Roundup: Induction and Coinduction (Slides by Davide Sangiorgi) DS2, 16. Juli 2024 in APB E005
Übung Summary and Outlook DS3, 17. Juli 2024 in APB E005


Kalender