zbMATH — the first resource for mathematics

Sequential and concurrent behaviour in Petri net theory. (English) Zbl 0669.68043
The authors examine the interleaved (occurrence sequence) behaviour semantics and the partial-order (process) semantics and the relationships between these semantics. An axiomatic approach to the definition of processes is compared with an inductive approach which relates processes to occurrence sequences. The comparison is done in the framework of Petri nets, because both types have already been formalized in different ways in net theory. The question of the ‘right’ set of axioms is discussed, and whether (and when) process semantics is more powerful than occurrence sequence semantics. To every theory, the full formal proof is given.
Reviewer: H.Fuss

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q65 Abstract data types; algebraic specification
06A06 Partial orders, general
93A10 General systems
94A15 Information theory (general)
Full Text: DOI
[1] Best, E., Relational semantics of concurrent programs (with some applications), (), 431-452
[2] Best, E., Concurrent behaviour: sequences, processes and axioms, (), 221-245
[3] Best, E.; Devillers, R., Concurrent behaviour: sequences, processes and programming languages, () · Zbl 0567.68035
[4] Best, E.; Devillers, R., Interleaving and partial orders in concurrency: a formal comparison, (), 299-323
[5] Best, E.; Fernández, C., Notations and terminology on Petri net theory, ()
[6] Best, E.; Randell, B., A formal model of atomicity in asynchronous systems, Acta inform., 16, 93-124, (1981) · Zbl 0511.68033
[7] ()
[8] Castellano, L., BETA-processes of C/E-systems, (), 83-100
[9] Devillers, R., The semantics of capacities in P/T-nets: a first look, Proc. 6th workshop on Petri nets Helsinki, (1985)
[10] Devillers, R., The expressive power of various enabling rules for P/T-nets, ()
[11] Fernández, C.; Nielsen, M.; Thiagarajan, P.S., A note on observable occurence nets, (), 122-138
[12] Genrich, H.J.; Lautenbach, K.; Thiagarajan, P.S., Elements of general net theory, (), 21-163 · Zbl 0441.68064
[13] Genrich, H.J.; Stankiewicz-Wiechno, E., A dictionary of some basic notions of net theory, (), 519-535
[14] Goltz, U.; Mycroft, A., On the relationship of CCS and Petri nets, (), 196-208
[15] Goltz, U.; Reisig, W., The non-sequential behaviour of Petri nets, Inform. and control, 57, 125-147, (1983) · Zbl 0551.68050
[16] Hannessy, M.; Plotkin, G., Full abstraction for a simple programming language, (), 108-120
[17] Holt, A.W., Final report on the project on information systems theory, Applied data research ADR6606, (1968)
[18] Lamport, L., What good is temporal logic?, (), 657-667
[19] Lauer, P.E., Synchronization of concurrent processes without globality assumptions, ACM SIGPLAN notices, 16, 9, 66-80, (1981)
[20] Lauer, P.E.; Shields, M.W.; Best, E., Formal theory of the basic COSY notation, (), upon Tyne · Zbl 0386.68025
[21] Mazurkiewicz, A., Concurrent program schemes and their interpretation, ()
[22] Milner, R., A calculus of communicating systems, () · Zbl 0452.68027
[23] Petri, C.A., Non-sequential processes, GMD-ISF rept. 77.05, (1977)
[24] Petri, C.A., Concurrency theory, (), 4-24, Advances in Petri nets 1986, Part I. Proc. of an advanced course, Bad Honnef 1986
[25] Plotkin, G., An operational semantics for CSP, (), 199-233 · Zbl 0512.68012
[26] Reisig, W., Petri nets, (1985), Springer Berlin · Zbl 0521.68057
[27] Reisig, W., Partial order semantics versus interleaving semantics of CSP-like languagesand its impact on fairness, (), 403-413
[28] Reisig, W., On the semantics of Petri nets, (), 347-372
[29] Shields, M.W., Adequate path expressions, (), 249-265 · Zbl 0429.68058
[30] Winskel, G., Event structure semantics for CCS and related languages, (), 561-576
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.