zbMATH — the first resource for mathematics

An event structure semantics for general Petri nets. (English) Zbl 0872.68126
Summary: 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-trivial and conservative extension of the (prime) event structure semantics of 1-safe Petri nets provided in M. Nielsen, G. Plotkin and G. Winskel [Theor. Comput Sci. 13, 85-108 (1981; Zbl 0452.68067)]. We also show that the strong relationship between prime event structures and 1-safe Petri nets established in a categorical framework in G. Winskel [Lect. Notes Comput. Sci. 255, 325-392 (1987; Zbl 0626.68022)]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.

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q55 Semantics in the theory of computing
68Q45 Formal languages and automata
Full Text: DOI
[1] Best, E.; Devillers, R., Sequential and concurrent behaviour in Petri net theory, Theoret. comput. sci., 55, 87-136, (1987) · Zbl 0669.68043
[2] Best, E.; Devillers, R.; Hall, J., The box calculus: a new causal algebra with multi-label communication, (), 21-69
[3] Boudol, G., Flow event structures and flow nets, (), 62-95
[4] Boudol, G.; Castellani, I., Permutation of transitions: an event structure semantics for CCS and SCCS, (), 411-427 · Zbl 0683.68029
[5] Devillers, R., Construction of S-invariants and S-components for refined Petri boxes, (), 242-261
[6] Droste, M., Event structures and domains, Theoret. comput. sci., 68, 37-47, (1989) · Zbl 0678.68080
[7] Ehrenfeucht, A.; Rozenberg, G., Partial (set) 2-structures; part II: state spaces of concurrent systems, Acta inform., 27, 343-368, (1990) · Zbl 0696.68083
[8] Engelfriet, J., Branching processes of Petri nets, Acta inform., 28, 575-591, (1991) · Zbl 0743.68106
[9] Hoogers, P.W., Behavioural aspects of Petri nets, () · Zbl 0826.68085
[10] Hoogers, P.W.; Kleijn, H.C.M.; Thiagarajan, P.S., A trace semantics for Petri nets, (), 595-604 · Zbl 0826.68085
[11] Hoogers, P.W.; Kleijn, H.C.M.; Thiagarajan, P.S., Local event structures and Petri nets, (), 462-476 · Zbl 0872.68126
[12] Meseguer, J.; Montanari, U., Petri nets are monoids, Inform. and comput., 88, 105-155, (1990) · Zbl 0711.68077
[13] Meseguer, J.; Montanari, U.; Sassone, V., On the semantics of Petri nets, (), 286-301
[14] Mukund, M., Petri nets and step transition systems, Internat. J. found. comput. sci., 3, 4, 443-478, (1992) · Zbl 0774.68086
[15] Nielsen, M.; Plotkin, G.; Winskel, G., Petri nets, event structures and domains, part I, Theoret. comput. sci., 13, 85-108, (1981) · Zbl 0452.68067
[16] Nielsen, M.; Rozenberg, G.; Thiagarajan, P.S., Elementary transition systems, Theoret. comput. sci., 96, 3-33, (1992) · Zbl 0759.68022
[17] Winskel, G., Categories of models for concurrency, (), 246-267
[18] Winskel, G., Petri nets, algebras, morphisms and compositionality, Inform. and comput., 72, 197-238, (1987) · Zbl 0622.68052
[19] Winskel, G., Event structures, (), 325-392
[20] Winskel, G., An introduction to event structures, (), 364-397
[21] Winskel, G.; Nielsen, M., Models for concurrency, (), 1-148
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.