Abstract
This paper argues that partial order semantics can be used profitably in the proofs of some nontrivial results in Petri net theory. We show that most of Commoner's and Hack's structure theory of free choice nets can be phrased and proved in terms of partial order behaviour. The new proofs are considerably shorter (and, arguably, more lucid) than the old ones; they also generalise the results from (safe) free choice nets to (bounded) extended free choice nets.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Best, E. and Devillers, R.: Sequential and Concurrent Behaviour in Petri Net Theory.TCS. 55 (1), 87–136 (1987).
Best, E. and Fernández, C.:Nonsequential Processes. A Petri Net View. Springer Monographs on Theoretical Computer Science, Vol. 13, 1988.
Best, E. and Thiagarajan, P. S.: Some Classes of Live and Safe Petri Nets. InConcurrency and Nets, K. Voss, H. J. Genrich and G. Rozenberg (eds), pp. 71–94, Springer-Verlag, 1987.
Commoner, F.: Deadlocks in Petri Nets. Report, Applied Data Inc., CA-7206-2311 (1972).
Desel, J.: Synchronie-Abstand in Stellen/Transitionen-Systemen. Diplomarbeit Arbeitspapiere der GMD Nr. 341, 1988.
Döpp, K.: Zum Hack'schen Wohlformungssatz für Free-Choice-Petrinetze.EIK, 19 (1–2), 3–15 (1983).
Esparza, J. and Silva, M.: Circuits, Handles, Bridges and Nets,10th Int. Conf. on Applications and Theory of Petri Nets, Bonn, pp. 134–153, 1989.
Goltz, U. and Reisig, W.: Weighted Synchronie Distances. InInformatik-Fachberichte 52: Application and Theory of Petri Nets, pp. 289–300, Springer-Verlag, 1982.
Goltz, U. and Reisig, W.: The Non-Sequential Behaviour of Petri Nets.Information and Control, 57 (2–3), 125–147 (1983).
Hack, M.:Analysis of Production Schemata by Petri Nets. TR-94, MIT-MAC, 1972.
Hack, M.:Corrections to MAC-TR-94. Computation Structure Notes 17, MIT-MAC, 1974.
Lu, W. M. and Merceron, A.: The Equivalence Between Well-behaved Bipolar Sychronisation Schemes and the Live and Safe Free Choice Nets Without Frozen Tokens,5th European Workshop on Application and Theory of Petri Nets, Århus, pp. 216–232, 1984.
Memmi, G. and Roucairol, G.:Linear Algebra in Net Theory. LNCS 84, pp. 213–220, Springer-Verlag, 1980.
Pratt, V.: Modelling of Concurrency with Partial Orders.Int. Journal of Parallel Processing, 15 (1), pp. 33–71 (1986).
Thiagarajan, P. S. and Voss, K.: A Fresh Look at Free Choice Nets.Information and Control, 61 (2), 85–113 (1984).
Author information
Authors and Affiliations
Additional information
Work partly done while both authors were with the Institut für Methodische Grundlagen, Gesellschaft für Mathematik und Datenverarbeitung, D-520S Sankt Augustin, and supported in part by Esprit Basic Research Action No. 3148: DEMON.
Rights and permissions
About this article
Cite this article
Best, E., Desel, J. Partial order behaviour and structure of Petri nets. Formal Aspects of Computing 2, 123–138 (1990). https://doi.org/10.1007/BF01888220
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01888220