zbMATH — the first resource for mathematics

A trace semantics for Petri nets (extended abstract). (English) Zbl 1427.68199
Kuich, Werner (ed.), Automata, languages and programming. 19th international colloquium, Wien, Austria, July 13–17, 1992. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 623, 595-604 (1992).
Summary: Our aim is to extend the semantic theory of elementary net systems [M. Nielsen et al., “Behavioural notions for elementary net systems”, Distrib. Comput. 4, No. 1, 45–57 (1990; doi:10.1007/BF01783665); Theor. Comput. Sci. 96, No. 1, 3–33 (1992; Zbl 0759.68022)] to general Petri nets. In doing so, we expect to obtain a theory which would reflect our intuition that general Petri nets are more expressive than elementary net systems (and for that matter, 1-safe Petri nets). As a first step, we provide a semantics for Petri nets using the theory of trace languages due to A. Mazurkiewicz [Lect. Notes Comput. Sci. 255, 279–324 (1987; Zbl 0633.68051)]. It turns out that in order to adequately treat the multiplicity of tokens in a Petri net, we must generalize the classical notions underlying trace languages along a number of directions. After doing so, it is easy to associate such a generalized trace language with each Petri net. We then characterize the class of trace languages – called PN-trace languages – that arise in this fashion. It turns out that the new trace languages can also be used to capture the behaviours of other models of concurrency. In particular, we characterize the general event structures of G. Winskel [Lect. Notes Comput. Sci. 255, 325–392 (1987; Zbl 0626.68022)] and their stable subclass in terms of our trace languages. One pleasant consequence of our results is that in this framework, 1-safe Petri nets, event structures, and general Petri nets constitute a strictly ascending chain in terms of expressive power.
For the entire collection see [Zbl 1369.68031].
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q55 Semantics in the theory of computing
Full Text: DOI
[1] Best, E., and Devillers, R., (1987), Sequential and concurrent behaviour in Petri net theory, Theoretical Computer Science 55, 87-136. · Zbl 0669.68043
[2] Best, E., and Fernández C., C., (1988), Nonsequential processes, EATCS Monographs on Theoretical Computer Science Vol. 13, Springer Verlag.
[3] Degano, P., Meseguer, J., and Montanari, U., (1989), Axiomatizing net computations and processes, In Proc. Logic in Computer Science, 175-185. · Zbl 0722.68085
[4] Ehrenfeucht, A., and Rozenberg, G., (1990), Partial 2-structures; part II: state spaces of concurrent systems, Acta Informatica, v. 27, 348-368. · Zbl 0696.68083
[5] Engelfriet, J., (1991), Branching processes of Petri nets, Acta Informatica, v.28, 575-591. · Zbl 0743.68106
[6] Goltz, U., and Mycroft, A., (1984), On the relationship of CCS and Petri nets, Lecture Notes in Computer Science 172, 196-208. · Zbl 0562.68049
[7] Goltz, U., and Reisig, W., (1983), The non-sequential behaviour of Petri nets, Information and Control 57, 125-147. · Zbl 0551.68050
[8] Goltz, U., and Reisig, W., (1985), CSP-programs as nets with individual tokens, Lecture Notes in Computer Science 188, 169-196. · Zbl 0571.68044
[9] Hoogers, P.W., Kleijn, H.C.M., and Thiagarajan, P.S., (1992), A trace semantics for Petri nets, Leiden University Techn. Rep. 92-03. · Zbl 0826.68085
[10] Mazurkiewicz, A., Trace theory, (1987), Lecture Notes in Computer Science 255, 279-324. · Zbl 0633.68051
[11] Mukund, M., (1991), A transition system characterization of Petri nets, Report TCS-91-02, School of Mathematics, SPIC Science Foundation, Madras, India.
[12] Nielsen, M., Plotkin, G., and Winskel, G., (1981), Petri nets, event structures and domains, part I, Theoretical Computer Science 13, 85-108. · Zbl 0452.68067
[13] Nielsen, M., Rozenberg, G., and Thiagarajan, P.S., (1990), Behavioural notions for elementary net systems, Distributed Computing 4, 45-57.
[14] Nielsen, M., Rozenberg, G., and Thiagarajan, P.S., (1990), Elementary transition systems, DAIMI-PB 310, Aarhus University, to appear in Theoretical Computer Science.
[15] Pratt, V.R., (1991), Modelling concurrency with geometry, In Proc. 18th Ann. ACM Symposium on Principles of Programming Languages, 311-322.
[16] Winskel, G.
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.