Polynomial Time Decidability of Monotone Liveness of Time Bounded AC/DC Nets

Atsushi OHTA; Kohkichi TSUJI

Polynomial Time Decidability of Monotone Liveness of Time Bounded AC/DC Nets

Atsushi OHTA, Kohkichi TSUJI

Full Text Views

0

Cite this

Summary :

Petri net is a mathematical model for concurrent systems. Liveness is one of important properties of Petri net. Liveness problem of general Petri net is of exponential space complexity and subclasses are suggested with less computational complexity. It is well known that liveness problem of bounded (extended) free choice net is solved in deterministic polynomial time. This paper treats liveness problem of AC/DC nets. AC/DC net is a subclass of Petri net that exhibits no confusion (mixture of concurrency and conflict). This class properly includes the class of free choice nets. It is shown that every minimal siphon of an AC/DC net is trap if and only if every strongly connected siphon is a trap. This result shows that monotone liveness of bounded AC/DC net is solved in deterministic polynomial time. It is shown that this result is true of bounded time AC/DC net with static fair condition.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.11 pp.2865-2870

Publication Date: 2001/11/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Concurrent Systems Technology)

Category

Cite this

Copy

Atsushi OHTA, Kohkichi TSUJI, "Polynomial Time Decidability of Monotone Liveness of Time Bounded AC/DC Nets" in IEICE TRANSACTIONS on Fundamentals, vol. E84-A, no. 11, pp. 2865-2870, November 2001, doi: .
Abstract: Petri net is a mathematical model for concurrent systems. Liveness is one of important properties of Petri net. Liveness problem of general Petri net is of exponential space complexity and subclasses are suggested with less computational complexity. It is well known that liveness problem of bounded (extended) free choice net is solved in deterministic polynomial time. This paper treats liveness problem of AC/DC nets. AC/DC net is a subclass of Petri net that exhibits no confusion (mixture of concurrency and conflict). This class properly includes the class of free choice nets. It is shown that every minimal siphon of an AC/DC net is trap if and only if every strongly connected siphon is a trap. This result shows that monotone liveness of bounded AC/DC net is solved in deterministic polynomial time. It is shown that this result is true of bounded time AC/DC net with static fair condition.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_11_2865/_p

Copy

@ARTICLE{e84-a_11_2865,
author={Atsushi OHTA, Kohkichi TSUJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Polynomial Time Decidability of Monotone Liveness of Time Bounded AC/DC Nets},
year={2001},
volume={E84-A},
number={11},
pages={2865-2870},
abstract={Petri net is a mathematical model for concurrent systems. Liveness is one of important properties of Petri net. Liveness problem of general Petri net is of exponential space complexity and subclasses are suggested with less computational complexity. It is well known that liveness problem of bounded (extended) free choice net is solved in deterministic polynomial time. This paper treats liveness problem of AC/DC nets. AC/DC net is a subclass of Petri net that exhibits no confusion (mixture of concurrency and conflict). This class properly includes the class of free choice nets. It is shown that every minimal siphon of an AC/DC net is trap if and only if every strongly connected siphon is a trap. This result shows that monotone liveness of bounded AC/DC net is solved in deterministic polynomial time. It is shown that this result is true of bounded time AC/DC net with static fair condition.},
keywords={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - Polynomial Time Decidability of Monotone Liveness of Time Bounded AC/DC Nets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2865
EP - 2870
AU - Atsushi OHTA
AU - Kohkichi TSUJI
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2001
AB - Petri net is a mathematical model for concurrent systems. Liveness is one of important properties of Petri net. Liveness problem of general Petri net is of exponential space complexity and subclasses are suggested with less computational complexity. It is well known that liveness problem of bounded (extended) free choice net is solved in deterministic polynomial time. This paper treats liveness problem of AC/DC nets. AC/DC net is a subclass of Petri net that exhibits no confusion (mixture of concurrency and conflict). This class properly includes the class of free choice nets. It is shown that every minimal siphon of an AC/DC net is trap if and only if every strongly connected siphon is a trap. This result shows that monotone liveness of bounded AC/DC net is solved in deterministic polynomial time. It is shown that this result is true of bounded time AC/DC net with static fair condition.
ER -