Project : Concurrency Theory
Dr. Carl Adam Petri, former honorary professor
Dr. Mark-Oliver Stehr, former research assistant
Dr. Olaf Kummer, former research assistant
Stefan Haar
Uwe Fenske
Duration: since 04/1994
Keywords:
Concurrency-Theorie, Axiome, Elementare Netz-Systeme, Zyklische Ordnungen, Markierte Graphen
Objectives:
The aim of this project is the investigation and coherent presentation of axiomatic concurrency theory. Axiomatic concurrency theory was originally proposed by C.A. Petri as a foundation for net theory based on the notions of causality and concurrency. Mathematically these two concepts are formalized as symmetric binary relations on the domain of (local) states and events. Physical considerations play a major role for the motivation of axioms and interpretation of results. The emphasis of this project is put on the analysis of interactions between different sets of axioms from a mathematical point of view.
An introduction to concurrency theory and in particular to the historical, philosophical and physical background is given by Hartmut Müller in Geschichte und Entwicklung der Concurrency Theorie. Also most of the original axiomatic systems and ideas of C.A.Petri are presented in this work.
In Physically Motivated Axiomatic Concurrency Theory - A Posetless Approach (and in the revised version Concurrency Theory of Cyclic and Acyclic Processes) Mark-Oliver Stehr treats concurrency theory without the assumption of an underlying partial order from which the causality relation is derived. In addition to (infinite) acyclic models this leads to consideration of cyclic but finite models leading to several difficulties. Furthermore this work explores the possibility of associating a net and even an elementary net system with the concurrency structure in a natural way. Some sufficient conditions for a succesfull connection between these worlds are proposed.
Olaf Kummer gave a coherent formal treatment of the subject in Axiomensysteme für die Theorie der Nebenläufigkeit. This work focuses on the difficulties (which are illustrated by strange models) arising in concurrency theory and presents possible solutions. For this task serveral new properties are formulated and their connections are explored. The work concludes with a comparison of different axiomatic systems. One of these shows a strong relation to the notion of D-continuity, which was developed by C.A.Petri as a (partial order) generalization of Dedekind continuity. In the meantime this work was also published as a book.
The work Zyklische Ordnungen - Axiome und einfache Eigenschaften by Mark-Oliver Stehr describes a mathematical theory of (partial) cyclic orders. This theory was developed by the author in order to cope with the problems arising when the underlying partial order structure of causality is given up and cyclic models are considered. Although this was the initial motivation, it seems that application for cyclic orders arise in several field where cyclic dependencies are relevant.
Publications:
- Hartmut Müller: Geschichte und Entwicklung der Concurrency Theorie. Diplomarbeit, Universität Hamburg, Fachbereich Informatik, 1993.
- Mark-Oliver Stehr: Physically Motivated Axiomatic Concurrency Theory - A Posetless Approach , Studienarbeit, Fachbereich Informatik, Universität Hamburg, December 1993.
-
Axiomensysteme für die Theorie der Nebenläufigkeit.
- Diplomarbeit, Universität Hamburg, Fachbereich Informatik, 1996.
- Logos Verlag, Berlin, 1996. ISBN 3-931216-28-4.
- Mark-Oliver Stehr: Zyklische Ordnungen - Axiome und einfache Eigenschaften , Diplomarbeit, Fachbereich Informatik, Universität Hamburg, 1996.
- Mark-Oliver Stehr: Concurrency Theory of Cyclic and Acyclic Processes , Fachbereichsbericht FBI-HH-B-190/96, Universität Hamburg, Fachbereich Informatik, September 1996.
- Olaf Kummer, Mark-Oliver Stehr: Petri's Axioms of Concurrency - A Selection of Recent Results , Proceedings of the 18th International Conference on Application and Theory of Petri Nets, Toulouse, June 23-27, 1997, Lecture Notes in Computer Science 1248, © Springer-Verlag , 1997