Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets

Toshimasa WATANABE; Satoshi TAOKA

doi:10.1587/transfun.E92.A.2707

Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets

Toshimasa WATANABE, Satoshi TAOKA

Full Text Views

0

Cite this

Summary :

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 Y^t A = and a T-invariant is a |T|-dimensional vector X with A X = 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.11 pp.2707-2716

Publication Date: 2009/11/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E92.A.2707

Type of Manuscript: Special Section INVITED PAPER (Special Section on Theory of Concurrent Systems and its Applications)

Category

Cite this

Copy

Toshimasa WATANABE, Satoshi TAOKA, "Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets" in IEICE TRANSACTIONS on Fundamentals, vol. E92-A, no. 11, pp. 2707-2716, November 2009, doi: 10.1587/transfun.E92.A.2707.
Abstract: 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 Y^t A = and a T-invariant is a |T|-dimensional vector X with A X = 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.2707/_p

Copy

@ARTICLE{e92-a_11_2707,
author={Toshimasa WATANABE, Satoshi TAOKA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets},
year={2009},
volume={E92-A},
number={11},
pages={2707-2716},
abstract={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 Y^t A = and a T-invariant is a |T|-dimensional vector X with A X = 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.},
keywords={},
doi={10.1587/transfun.E92.A.2707},
ISSN={1745-1337},
month={November},}

Copy

TY - JOUR
TI - Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2707
EP - 2716
AU - Toshimasa WATANABE
AU - Satoshi TAOKA
PY - 2009
DO - 10.1587/transfun.E92.A.2707
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2009
AB - 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 Y^t A = and a T-invariant is a |T|-dimensional vector X with A X = 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.
ER -