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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Atsushi OHTA, Kohkichi TSUJI, "Computational Complexity of Liveness Problem of Normal Petri Net" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 11, pp. 2717-2722, November 2009, doi: 10.1587/transfun.E92.A.2717.
Abstract: Petri net is a powerful modeling tool for concurrent systems. Liveness, which is a problem to verify there exists no local deadlock, is one of the most important properties of Petri net to analyze. Computational complexity of liveness of a general Petri net is deterministic exponential space. Liveness is studied for subclasses of Petri nets to obtain necessary and sufficient conditions that need less computational cost. These are mainly done using a subset of places called siphons. CS-property, which denotes that every siphon has token(s) in every reachable marking, in one of key properties in liveness analysis. On the other hand, normal Petri net is a subclass of Petri net whose reachability set can be effectively calculated. This paper studies computational complexity of liveness problem of normal Petri nets. First, it is shown that liveness of a normal Petri net is equivalent to cs-property. Then we show this problem is co-NP complete by deriving a nondeterministic algorithm for non-liveness which is similar to the algorithm for liveness suggested by Howell et al. Lastly, we study structural feature of bounded Petri net where liveness and cs-property are equivalent. From this consideration, liveness problem of bounded normal Petri net is shown to be deterministic polynomial time complexity.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.2717/_p
Copier
@ARTICLE{e92-a_11_2717,
author={Atsushi OHTA, Kohkichi TSUJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computational Complexity of Liveness Problem of Normal Petri Net},
year={2009},
volume={E92-A},
number={11},
pages={2717-2722},
abstract={Petri net is a powerful modeling tool for concurrent systems. Liveness, which is a problem to verify there exists no local deadlock, is one of the most important properties of Petri net to analyze. Computational complexity of liveness of a general Petri net is deterministic exponential space. Liveness is studied for subclasses of Petri nets to obtain necessary and sufficient conditions that need less computational cost. These are mainly done using a subset of places called siphons. CS-property, which denotes that every siphon has token(s) in every reachable marking, in one of key properties in liveness analysis. On the other hand, normal Petri net is a subclass of Petri net whose reachability set can be effectively calculated. This paper studies computational complexity of liveness problem of normal Petri nets. First, it is shown that liveness of a normal Petri net is equivalent to cs-property. Then we show this problem is co-NP complete by deriving a nondeterministic algorithm for non-liveness which is similar to the algorithm for liveness suggested by Howell et al. Lastly, we study structural feature of bounded Petri net where liveness and cs-property are equivalent. From this consideration, liveness problem of bounded normal Petri net is shown to be deterministic polynomial time complexity.},
keywords={},
doi={10.1587/transfun.E92.A.2717},
ISSN={1745-1337},
month={November},}
Copier
TY - JOUR
TI - Computational Complexity of Liveness Problem of Normal Petri Net
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2717
EP - 2722
AU - Atsushi OHTA
AU - Kohkichi TSUJI
PY - 2009
DO - 10.1587/transfun.E92.A.2717
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2009
AB - Petri net is a powerful modeling tool for concurrent systems. Liveness, which is a problem to verify there exists no local deadlock, is one of the most important properties of Petri net to analyze. Computational complexity of liveness of a general Petri net is deterministic exponential space. Liveness is studied for subclasses of Petri nets to obtain necessary and sufficient conditions that need less computational cost. These are mainly done using a subset of places called siphons. CS-property, which denotes that every siphon has token(s) in every reachable marking, in one of key properties in liveness analysis. On the other hand, normal Petri net is a subclass of Petri net whose reachability set can be effectively calculated. This paper studies computational complexity of liveness problem of normal Petri nets. First, it is shown that liveness of a normal Petri net is equivalent to cs-property. Then we show this problem is co-NP complete by deriving a nondeterministic algorithm for non-liveness which is similar to the algorithm for liveness suggested by Howell et al. Lastly, we study structural feature of bounded Petri net where liveness and cs-property are equivalent. From this consideration, liveness problem of bounded normal Petri net is shown to be deterministic polynomial time complexity.
ER -