Paper Info
Title
Computational Complexity Of Liveness Problem Of Normal Petri Net
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.
Year
DOI
Venue
2009
10.1587/transfun.E92.A.2717
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
Keywords
Field
DocType
concurrent system, Petri net, liveness, computational complexity
Discrete mathematics,Petri net,Nondeterministic algorithm,Deadlock,Algorithm,Stochastic Petri net,Theoretical computer science,Reachability,Process architecture,Mathematics,Liveness,Computational complexity theory
Journal
Volume
Issue
ISSN
E92A
11
0916-8508
Citations 
PageRank 
References 
3
0.41
6
Authors
2
Name
Order
Citations
PageRank
atsushi ohta16615.31
Kohkichi Tsuji232.44