Polynomial Time Decidability of Monotone Liveness of Time Bounded AC/DC Nets(Special Section on Concurrent Systems Technology)

スポンサーリンク

概要

• 論文の詳細を見る

• Petri net is a methematical 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.

• 社団法人電子情報通信学会の論文
• 2001-11-01

著者

• Tsuji Kohkichi

  The Faculty Of Information Science And Technology Aichi Prefectural University

• OHTA Atsushi

  the Faculty of Information Science and Technology, Aichi Prefectural University

• Ohta Atsushi

  The Faculty Of Information Science And Technology Aichi Prefectural University

関連論文

• Turing Machine Equivalence of Time Asymmetric Choice Nets (Special Section on Concurrent Systems Technology)
• Polynomial Time Decidability of Monotone Liveness of Time Bounded AC/DC Nets(Special Section on Concurrent Systems Technology)

スポンサーリンク