La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Computational Complexity of Liveness Problem of Normal Petri Net Complexité informatique du problème de vivacité d'un réseau de Petri normal

Atsushi OHTA, Kohkichi TSUJI

  • Vues en texte intégral

    0

  • Citer

Résumé:

Le réseau de Petri est un puissant outil de modélisation pour les systèmes concurrents. La vivacité, qui est un problème pour vérifier qu'il n'existe pas de blocage local, est l'une des propriétés les plus importantes à analyser du réseau de Petri. La complexité informatique de la vivacité d'un réseau de Petri général est un espace exponentiel déterministe. La vivacité est étudiée pour des sous-classes de réseaux de Petri afin d'obtenir des conditions nécessaires et suffisantes nécessitant moins de coûts de calcul. Celles-ci se font principalement à l’aide d’un sous-ensemble d’endroits appelés siphons. Propriété CS, qui indique que chaque siphon a un ou plusieurs jetons dans chaque marquage accessible, dans l'une des propriétés clés de l'analyse d'activité. D'un autre côté, le réseau de Petri normal est une sous-classe du réseau de Petri dont l'ensemble d'accessibilité peut être calculé efficacement. Cet article étudie la complexité informatique du problème de vivacité des réseaux de Petri normaux. Premièrement, il est montré que la vivacité d’un réseau de Petri normal est équivalente à la propriété cs. Ensuite, nous montrons que ce problème est co-NP complet en dérivant un algorithme non déterministe pour la non-vivance qui est similaire à l'algorithme pour la vivacité suggéré par Howell et al. Enfin, nous étudions les caractéristiques structurelles du réseau de Petri borné où la vivacité et la propriété cs sont équivalentes. À partir de cette considération, le problème de vivacité du réseau de Petri normal borné se révèle être une complexité temporelle polynomiale déterministe.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.11 pp.2717-2722
Date de publication
2009/11/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E92.A.2717
Type de manuscrit
Special Section PAPER (Special Section on Theory of Concurrent Systems and its Applications)
Catégories

Auteurs

Mots-clés

Table des matières