The search functionality is under construction.

The search functionality is under construction.

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

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, "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 -