Finding Minimal Siphons in General Petri Nets (Special Section on Description Models for Concurrent Systems and Their Applications)
スポンサーリンク
概要
- 論文の詳細を見る
A siphon (or alternatively a structural deadlock)of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that any proper subset is not a siphon. The results of the paper are as follows.(1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete.(2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal class of mutually disjoint minimal siphons of a general Petri net is proposed.
- 社団法人電子情報通信学会の論文
- 1996-11-25
著者
-
Yamauchi M
Pharmaceutical Research Institute Kyowa Hakko Kogyo Co. Ltd.
-
Yamauchi M
School Of Engineering Kinki University
-
Watanabe Toshimasa
Hiroshima University
-
Watanabe Toshimasa
The Department Of Circuits And Systems Faculty Of Engineering Hiroshima University
-
Watanabe Toshimasa
Hiroshima Univ. Higashi‐hiroshima Jpn
-
TANIMOTO Shinji
the Department of Circuits and Systems, Faculty of Engineering, Hiroshima University
-
YAMAUCHI Masahiro
Faculty of Engineering
-
Tanimoto S
Hiroshima Univ. Higashi‐hiroshima
-
Watanabe Toshimasa
Hiroshima Univ. Higashihiroshima‐shi Jpn
-
TANIMOTO Shinji
the Department of Circuits and Systems
関連論文
- Time Complexity Analysis of the Minimal Siphon Extraction Problem of Petri Nets (Special Section on Concurrent Systems Technology)
- Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets
- Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets(Concurrent/Hybrid Systems : Theory and Applications)
- Experimental Evaluation of Two Algorithms for Computing Petri Net Invariants(Special Section on Concurrent Systems Technology)
- Evaluation of the Carrier Potential for the Lipid Dispersion System with Lipophilic Compound
- Role of the Lipid Emulsion on an Injectable Formulation of Lipophilic KW-3902, a Newly Synthesized Adenosine A_1-Receptor Antagonist
- Formulation Development of a Filter-Sterilizable Lipid Emulsion for Lipophilic KW-3902, a Newly Synthesized Adenosine A_1-Receptor Antagonist
- Enhancing PC Cluster-Based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem
- Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs
- Performance Comparison of Algorithms for the Dynamic Shortest Path Problem(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
- On the Legal Firing Sequence Problem of Petri Nets with Cactus Structure (Special Section of Selected Papers from the 12th Workshop on Circuit and Systems in Karuizawa)
- Assignment of the C K-Shell Photoabsorption Spectrum of CF_3CN Molecule
- Finding a Minimal Siphon Containing Specified Places in a General Petri Net (Special Section on Description Models for Concurrent Systems and Their Applications)
- Finding Minimal Siphons in General Petri Nets (Special Section on Description Models for Concurrent Systems and Their Applications)
- The Legal Firing Sequence Problem of Petri Nets(Special Issue on Algorithm Engineering : Surveys)
- A linear time algorithm for tri-connectivity augmentation of bi-connected graphs with upper bounds on vertex-degree increase (第21回 回路とシステム軽井沢ワークショップ論文集) -- (グラフアルゴリズム)
- On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
- Bi-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree Increase(Graph Algorithm, Foundations of Computer Science)
- A 2-Approximation Algorithm to (k+1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph(Discrete Mathematics and Its Applications)
- A Linear Time Algorithm for Bi-Connectivity Augmentation of Graphs with Upper Bounds on Vertex-Degree Increase(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
- Extracting Minimal Siphon-Traps of Petri Nets and Its Application to Computing Nonnegative Integer-Invariants(Special Section on Concurrent System Technology and Its Application to Multiple Agent Systems)
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints
- Optical resolution by replacing crystallization of ammonium salts of N-acetyl-DL-2-aminobutanoic acid, N-acetyl-DL-norvaline, and N-acetyl-DL-norleucine.
- Optical resolution by replacing crystallization of DL-threonine.