Médésu Sogbohossou ; Antoine Vianou - Un dépliage par processus pour calculer le préfixe complet des réseaux de Petri

arima:3177 - Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, 24 juillet 2017, Volume 27 - 2017 - Numéro spécial CARI 2016 - https://doi.org/10.46298/arima.3177
Un dépliage par processus pour calculer le préfixe complet des réseaux de PetriArticle

Auteurs : Médésu Sogbohossou ; Antoine Vianou

    [en]
    The partial-order technique of the unfolding implicitly represents state-space of a Petri net (PN), by in particular preserving the concurrency relations between the events. That makes it possible to contain state-space explosion problem in case of strong concurrency. A complete prefix of unfolding is used to cover all the state-space of a bounded PN: its computation according to the classical approach is based on the concept of adequate order, taking directly into account only safe PN. In this paper, a new approach independent of the concept of adequate order and faithful to the partial-order semantics, consists in creating the events of the unfolding in the context of a single process at the same time. The results of the tests are conclusive for safe and nonsafe PN. Some solutions are presented to improve compactness of the prefix obtained.

    [fr]
    La technique d'ordre partiel du dépliage représente implicitement l'espace d'état d'un réseau de Petri (RdP), en conservant notamment les relations de concurrence entre les événements. Cela permet de contenir le phénomène de l'explosion combinatoire en cas de forte concurrence. Un préfixe complet de dépliage sert à couvrir tout l'espace d'état d'un RdP borné: son calcul suivant l'approche classique se base sur le concept d'ordre adéquat, ne prenant directement en compte que les RdP saufs. Dans cet article, une nouvelle approche indépendante du concept d'ordre adéquat et fidèle à la sémantique d'ordre partiel, consiste à créer les événements du dépliage dans le contexte d'un unique processus à la fois. Les résultats des tests sont concluants pour les RdP saufs et non saufs. Des solutions sont présentées pour améliorer la compacité du préfixe obtenu.


    Volume : Volume 27 - 2017 - Numéro spécial CARI 2016
    Publié le : 24 juillet 2017
    Accepté le : 4 juillet 2017
    Soumis le : 8 mars 2017
    Mots-clés : [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], [en] bounded Petri nets, complete prefix of unfolding, adequate order, alternative processes; [fr] réseaux de Petri bornés, préfixe complet de dépliage, ordre adéquat, processus alternatifs

    Statistiques de consultation

    Cette page a été consultée 736 fois.
    Le PDF de cet article a été téléchargé 644 fois.