The search functionality is under construction.

The search functionality is under construction.

We consider only P-invariants that are nonnegative integer vectors in this paper. An *P-invariant* of a Petri net *N*=(*P*,*T*,*E*,α,β) is a |*P*|-dimensional vector *Y* with *Y*^{t} *A* = *A* of *N*. The *support* of an invariant is the set of elements having nonzero values in the vector. Since any invariant is expressed as a linear combination of minimal-support invariants (ms-invariants for short) with nonnegative rational coefficients, it is usual to try to obtain either several invariants or the set of all ms-invariants. The *Fourier-Motzkin* method (*FM*) is well-known for computing a set of invariants including all ms-invariants. It has, however, critical deficiencies such that, even if invariants exist, none of them may be computed because of memory overflow caused by storing candidate vectors for invariants and such that, even when a set of invariants are produced, many non-ms invariants may be included. We are going to propose the following two methods: (1) FM1_M2 that finds a smallest possible set of invariants including all ms-invariants; (2) STFM that necessarily produces one or more invariants if they exist. Experimental results are given to show their superiority over existing ones.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.11 pp.2871-2880

- Publication Date
- 2001/11/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on Concurrent Systems Technology)

- Category

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.

Copy

Katsushi TAKANO, Satoshi TAOKA, Masahiro YAMAUCHI, Toshimasa WATANABE, "Experimental Evaluation of Two Algorithms for Computing Petri Net Invariants" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 11, pp. 2871-2880, November 2001, doi: .

Abstract: We consider only P-invariants that are nonnegative integer vectors in this paper. An *P-invariant* of a Petri net *N*=(*P*,*T*,*E*,α,β) is a |*P*|-dimensional vector *Y* with *Y*^{t} *A* = *A* of *N*. The *support* of an invariant is the set of elements having nonzero values in the vector. Since any invariant is expressed as a linear combination of minimal-support invariants (ms-invariants for short) with nonnegative rational coefficients, it is usual to try to obtain either several invariants or the set of all ms-invariants. The *Fourier-Motzkin* method (*FM*) is well-known for computing a set of invariants including all ms-invariants. It has, however, critical deficiencies such that, even if invariants exist, none of them may be computed because of memory overflow caused by storing candidate vectors for invariants and such that, even when a set of invariants are produced, many non-ms invariants may be included. We are going to propose the following two methods: (1) FM1_M2 that finds a smallest possible set of invariants including all ms-invariants; (2) STFM that necessarily produces one or more invariants if they exist. Experimental results are given to show their superiority over existing ones.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_11_2871/_p

Copy

@ARTICLE{e84-a_11_2871,

author={Katsushi TAKANO, Satoshi TAOKA, Masahiro YAMAUCHI, Toshimasa WATANABE, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Experimental Evaluation of Two Algorithms for Computing Petri Net Invariants},

year={2001},

volume={E84-A},

number={11},

pages={2871-2880},

abstract={We consider only P-invariants that are nonnegative integer vectors in this paper. An *P-invariant* of a Petri net *N*=(*P*,*T*,*E*,α,β) is a |*P*|-dimensional vector *Y* with *Y*^{t} *A* = *A* of *N*. The *support* of an invariant is the set of elements having nonzero values in the vector. Since any invariant is expressed as a linear combination of minimal-support invariants (ms-invariants for short) with nonnegative rational coefficients, it is usual to try to obtain either several invariants or the set of all ms-invariants. The *Fourier-Motzkin* method (*FM*) is well-known for computing a set of invariants including all ms-invariants. It has, however, critical deficiencies such that, even if invariants exist, none of them may be computed because of memory overflow caused by storing candidate vectors for invariants and such that, even when a set of invariants are produced, many non-ms invariants may be included. We are going to propose the following two methods: (1) FM1_M2 that finds a smallest possible set of invariants including all ms-invariants; (2) STFM that necessarily produces one or more invariants if they exist. Experimental results are given to show their superiority over existing ones.

keywords={},

doi={},

ISSN={},

month={November},}

Copy

TY - JOUR

TI - Experimental Evaluation of Two Algorithms for Computing Petri Net Invariants

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 2871

EP - 2880

AU - Katsushi TAKANO

AU - Satoshi TAOKA

AU - Masahiro YAMAUCHI

AU - Toshimasa WATANABE

PY - 2001

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E84-A

IS - 11

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - November 2001

AB - We consider only P-invariants that are nonnegative integer vectors in this paper. An *P-invariant* of a Petri net *N*=(*P*,*T*,*E*,α,β) is a |*P*|-dimensional vector *Y* with *Y*^{t} *A* = *A* of *N*. The *support* of an invariant is the set of elements having nonzero values in the vector. Since any invariant is expressed as a linear combination of minimal-support invariants (ms-invariants for short) with nonnegative rational coefficients, it is usual to try to obtain either several invariants or the set of all ms-invariants. The *Fourier-Motzkin* method (*FM*) is well-known for computing a set of invariants including all ms-invariants. It has, however, critical deficiencies such that, even if invariants exist, none of them may be computed because of memory overflow caused by storing candidate vectors for invariants and such that, even when a set of invariants are produced, many non-ms invariants may be included. We are going to propose the following two methods: (1) FM1_M2 that finds a smallest possible set of invariants including all ms-invariants; (2) STFM that necessarily produces one or more invariants if they exist. Experimental results are given to show their superiority over existing ones.

ER -