Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets
-
- WATANABE Toshimasa
- Graduate School of Engineering, Hiroshima University
-
- TAOKA Satoshi
- Graduate School of Engineering, Hiroshima University
この論文をさがす
抄録
Invariants of Petri nets are fundamental algebraic characteristics of Petri nets, and are used in various situations, such as checking (as necessity of) liveness, boundedness, periodicity and so on. Any given Petri net N has two kinds of invariants: a P-invariant is a |P|-dimensional vector Y with Yt·A = 0 and a T-invariant is a |T|-dimensional vector X with A · X =0 for the place-transition incidence matrix A of N. T-invariants are nonnegative integer vectors, while this is not always the case with P-invariants. This paper deals only with nonnegative integer invariants (invariants that are nonnegative vectors) and shows results common to the two invariants. For simplicity of discussion, only P-invariants are treated. The Fourier-Motzkin method is well-known for computing all minimal support integer invariants. This method, however, has a critical deficiency such that, even if a given Perti net N has any invariant, it is likely that no invariants are obtained because of an overflow in storing intermediate vectors as candidates for invariants. The subject of the paper is to give an overview and results known to us for efficiently computing minimal-support nonnegative integer invariants of a given Petri net by means of the Fourier-Motzkin method. Also included are algorithms for efficiently extracting siphon-traps of a Petri net.
収録刊行物
-
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E92-A (11), 2707-2716, 2009
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390001206310197760
-
- NII論文ID
- 10026860688
-
- NII書誌ID
- AA10826239
-
- ISSN
- 17451337
- 09168508
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用不可