The search functionality is under construction.
The search functionality is under construction.

Computational Complexity of Liveness Problem of Normal Petri Net

Atsushi OHTA, Kohkichi TSUJI

  • Full Text Views

    0

  • Cite this

Summary :

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.11 pp.2717-2722
Publication Date
2009/11/01
Publicized
Online ISSN
1745-1337
DOI
10.1587/transfun.E92.A.2717
Type of Manuscript
Special Section PAPER (Special Section on Theory of Concurrent Systems and its Applications)
Category

Authors

Keyword