The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Le réseau de Petri est un modèle mathématique pour les systèmes concurrents. La vivacité est l’une des propriétés importantes du réseau de Petri. Le problème de vivacité du réseau de Petri général est d'une complexité spatiale exponentielle et les sous-classes sont suggérées avec moins de complexité informatique. Il est bien connu que le problème de vivacité d’un réseau de libre choix limité (étendu) est résolu en temps polynomial déterministe. Cet article traite du problème de vivacité des réseaux AC/DC. AC/DC net est une sous-classe du réseau Petri qui ne présente aucune confusion (mélange de concurrence et de conflit). Cette classe inclut à juste titre la classe des moustiquaires à libre choix. Il est montré que tout siphon minimal d’un réseau AC/DC est un piège si et seulement si tout siphon fortement connecté est un piège. Ce résultat montre que la vivacité monotone du réseau AC/DC borné est résolue en temps polynomial déterministe. Il est montré que ce résultat est vrai pour un temps limité AC/DC net avec des conditions statiques acceptables.
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.
Copier
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
Copier
@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},}
Copier
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 -