×
Finkel, Alain; Petrucci, Laure

Composition/decomposition of Petri nets and their covering graphs. (Composition/décomposition de réseaux de Petri et de leurs graphes de couverture.) (French) Zbl 0890.68088

RAIRO, Inform. Théor. Appl. 28, No. 2, 73-124 (1994).
We study composition and decomposition of Petri nets via a common set of places or transitions. We prove that some properties are preserved by these techniques, and some other ones can be obtained by the composition of the covering graphs. We propose some algorithms to decompose a net according to the properties that must be verified. We present an algorithm to compose minimal covering graphs, less expensive than a straightforward construction, concerning time as well as space.

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68W35 Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)

Keywords:

Petri nets; minimal covering graphs
PDF BibTeX XML Cite
\textit{A. Finkel} and \textit{L. Petrucci}, RAIRO, Inform. Théor. Appl. 28, No. 2, 73--124 (1994; Zbl 0890.68088)
Full Text: DOI EuDML

References:

[1] 1. A. BOURGUET, Étude de la concordance de comportement de deux réseaux de Petri. Application à la validation des protocoles : détection automatique des erreurs de conception. Thèse de l’Université Pierre-et-Marie-Curie, septembre 1990.
[2] 2. G. BERTHELOT, L. PETRUCCI, Putting Algebraic Nets Into Practice, Rapport interne CEDRIC-IIE, janvier 1989.
[3] 3. GW. BRAMS, Réseaux de Petri : théorie et pratique, Masson, 1983. Zbl0501.68027 · Zbl 0501.68027
[4] 4. W. BRAUER, W. REISIG, G. ROSENBERG, Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Zbl0619.00023 · Zbl 0619.00023
[5] Part 1, Proceedings of an Advanced Course at Bad Honnef, in LNCS No. 254, Springer Verlag, 1986.
[6] 5. C. DIMITROVICI, U. HUMMERT, L. PETRUCCI, The Properties of Algebraic Nets Schemes in Some Semantics, Proceedings of the llth International Conference on Application and Theory of Petri Nets, Paris, juin 1990.
[7] 6. A. FINKEL, The Minimal Coverability Graph for Petri Nets. Advances in Petri Nets 1993, LNCS 674, pp. 210-243, Springer Verlag, 1993. MR1250615
[8] 7. M. HACK, Decidability Questions for Petri Nets, Ph. D. Thesis, Technical Report 161, MIT, Laboratory for Computer Science, juin 1976. · Zbl 0357.68038
[9] 8. G. MEMMI, J. VAUTHERIN, Analysing Nets by the Invariant Méthode, Advances in Petri Nets 1986, LNCS 255, pp. 300-337, Springer Verlag, 1987. Zbl0658.68068 MR902661 · Zbl 0658.68068
[10] 9. W. REISIG, Petri Nets, Springer Verlag, 1985. Zbl0555.68033 MR782303 · Zbl 0555.68033
[11] 10. Y. SOUISSI, Une étude de la préservation de propriétés par composition de réseaux de Petri, Thèse de l’Université Pierre-et-Marie-Curie, février 1990.
[12] 11. A. VALMARI, Compositional State Space Generation, Proceedings of the 11th International Conference on Application and Theory of Petri Nets, Paris, juin 1990.
[13] 12. J. VAUTHERIN, Un modèle algébrique, basé sur les réseaux de Petri, pour l’étude des systèmes parallèles, Thèse de doctorat d’ingénieur, Université de Paris-Sud, Centre d’Orsay, juin 1985.
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.