In: Theoretical Computer Science, Vol. 153, No. 1--2, pages 129-170. 1996.
Abstract: In this paper we address the following question: What type of event structures are suitable for representing the behaviour of general Petri nets? As a partial answer to this question we define a new class of event structures called `local event structures' and identify a subclass called `UL-event structures'. We propose that UL-event structures are appropriate for capturing the behaviour of general Petri nets. Our answer is a partial one in that in the proposed event structure semantics, auto-concurrency is filtered out from the behaviour of Petri nets. It turns out that this limited event structure semantics for Petri nets is nevertheless a non-trival and conservative extension of the (prime) event structure semantics of 1-safe Petri nets provided in Nielsen et al. (1981). We also show that the strong relationship between prime event structures and 1-safe Petri nets established in a categorical framework in Winskel (1987) can be extended to the present setting, provided we restrict our attention to the subclass of Petri nets whose behaviours do not exhibit any auto-concurrency. Finally, we show that Winskel's general and stable event structures can be smoothly related to local event structures and that similarly prime event structures can be related to UL-event structures.
Back to the Petri Nets Bibliography