The search functionality is under construction.

The search functionality is under construction.

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

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.

Copy

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

Copy

@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},}

Copy

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 -