Petri Algebras

Eric Badouel 1 Jules Chenou 2 Goulven Guillou 3
1 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
3 Lab-STICC_UBO_CACS_MOCS
UBO - Université de Brest, Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
Abstract : The firing rule of Petri nets relies on a residuation operation for the commutative monoid of natural number. We identify a class of residuated commutative monoids, called Petri algebras, for which one can mimic the token game of Petri nets to define the behaviour of generalized Petri net whose flow relation and place contents are valued in such algebraic structures. The sum and its associated residuation capture respectively how resources within places are produced and consumed through the firing of a transition. We show that Petri algebras coincide with the positive cones of lattice-ordered commutative groups and constitute the subvariety of the (duals of) residuated lattices generated by the commutative monoid of natural number. We however exhibit a Petri algebra whose corresponding class of nets is strictly more expressive than the class of Petri nets. More precisely, we introduce a class of nets, termed lexicographic Petri nets, that are associated with the positive cones of the lexicographic powers of the additive group of real numbers. This class of nets is universal in the sense that any net associated with some Petri algebras canbe simulated by a lexicographic Petri net. All the classical decidable properties of Petri nets however (termination, covering, boundedness, structural boundedness, accessibility, deadlock, liveness ...) are undecidable on the class of lexicographic Petri nets. Finally we turn our attentionto bounded nets associated with Petri algebras and show that their dynamic can be reformulated in term of MV-algebras.
Type de document :
Rapport
[Research Report] RR-5355, INRIA. 2004, pp.28
Liste complète des métadonnées

https://hal.inria.fr/inria-00070648
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 19 mai 2006 - 21:06:48
Dernière modification le : jeudi 29 novembre 2018 - 16:53:03
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:39:18

Fichiers

Identifiants

  • HAL Id : inria-00070648, version 1

Citation

Eric Badouel, Jules Chenou, Goulven Guillou. Petri Algebras. [Research Report] RR-5355, INRIA. 2004, pp.28. 〈inria-00070648〉

Partager

Métriques

Consultations de la notice

479

Téléchargements de fichiers

169