ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 28/9 - 2009  - pp.1107-1142  - doi:10.3166/tsi.28.1107-1142
TITRE
Le problème de couverture pour les réseaux de Petri. Résultats classiques et développements récents

RÉSUMÉ
Les réseaux de Petri sont une classe bien étudiée de modèles propres à représenter les comportements de systèmes informatiques concurrents. Dans ce cadre, le problème de couverture (étant donné un marquage m, existe-t-il un marquage accessible qui assigne à chaque place du réseau au moins autant de jetons que m ?) est de tout premier intérêt, car de nombreuses propriétés de sûreté (toutes les exécutions du système restent-elles dans un ensemble de bons états ?) peuvent y être ramenées. De nombreux travaux ont récemment été consacrés à l'étude d'algorithmes efficaces pour résoudre le problème de couverture. Dans cet article, nous survolons plusieurs de ces travaux classiques ou récents : l'algorithme de Karp et Miller et un algorithme efficace en pratique, qui résolvent le problème de couverture en calculant un ensemble de couverture du réseau ; l'approche « en arrière » d'Abdulla et al. ; et l'approche « en avant » Expand, Enlarge and Check. Pour finir, nous présentons une nouvelle approche combinant les forces des méthodes « en avant » et « en arrière ».


ABSTRACT
Petri nets are a widespread class of models to represent behaviours of concurrent systems. An important problem on Petri nets is the coverability problem (does there exist a reachable marking that assigns to each place at least as many tokens as a given marking m?), mainly because many safety properties (does the system always stay inside a set of good behaviours?) can be reduced to it. Many recent works have been devoted to the study of efficient algorithms to decide the coverability problem. In this paper, we survey several of these classical or recent works: the Karp and Miller algorithm and an efficient algorithm, that both solve the coverability problem by computing the coverability set of the net; the "backward" approach of Abdulla et al.; and the Expand, Enlarge and Check "forward" approach. We close the paper by discussing a new method combining the strengths of the forward and backward methods.


AUTEUR(S)
Pierre GANTY, Gilles GEERAERTS, Jean-Pierre RASKIN, L. VAN BEGIN

MOTS-CLÉS
réseaux de Petri, problème de couverture.

KEYWORDS
Petri nets, coverability problem.

CITATIONS
tsi.revuesonline.com/revues/11/citation/14022.html

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (432 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier