ALGORITHM FOR THE GENERAL PETRI NET REACHABILITY PROBLEM.

Ernst W. Mayr

doi:10.1137/0213029

ALGORITHM FOR THE GENERAL PETRI NET REACHABILITY PROBLEM.

Ernst W. Mayr

Stanford University

Research output: Contribution to journal › Article › peer-review

376 Scopus citations

Abstract

An algorithm is presented for the general Petri net reachability problem. It is based on a generalization of the basic reachability tree construction which is made symmetric with respect to the initial and final marking. Sets of transition sequences described by finite automata are used for approximations to firing sequences, and the approximation error is assessed by Presburger expressions. The approximation algorithm is iterated until a sufficient criterion for reachability is satisfied. The exact computational complexity of the algorithm is an open problem.

Original language	English
Pages (from-to)	441-460
Number of pages	20
Journal	SIAM Journal on Computing
Volume	13
Issue number	3
DOIs	https://doi.org/10.1137/0213029
State	Published - 1984
Externally published	Yes

Access to Document

10.1137/0213029

Cite this

@article{a88dbe8f9feb4799bd9a8d296595776b,

title = "ALGORITHM FOR THE GENERAL PETRI NET REACHABILITY PROBLEM.",

abstract = "An algorithm is presented for the general Petri net reachability problem. It is based on a generalization of the basic reachability tree construction which is made symmetric with respect to the initial and final marking. Sets of transition sequences described by finite automata are used for approximations to firing sequences, and the approximation error is assessed by Presburger expressions. The approximation algorithm is iterated until a sufficient criterion for reachability is satisfied. The exact computational complexity of the algorithm is an open problem.",

author = "Mayr, \{Ernst W.\}",

year = "1984",

doi = "10.1137/0213029",

language = "English",

volume = "13",

pages = "441--460",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - ALGORITHM FOR THE GENERAL PETRI NET REACHABILITY PROBLEM.

AU - Mayr, Ernst W.

PY - 1984

Y1 - 1984

N2 - An algorithm is presented for the general Petri net reachability problem. It is based on a generalization of the basic reachability tree construction which is made symmetric with respect to the initial and final marking. Sets of transition sequences described by finite automata are used for approximations to firing sequences, and the approximation error is assessed by Presburger expressions. The approximation algorithm is iterated until a sufficient criterion for reachability is satisfied. The exact computational complexity of the algorithm is an open problem.

AB - An algorithm is presented for the general Petri net reachability problem. It is based on a generalization of the basic reachability tree construction which is made symmetric with respect to the initial and final marking. Sets of transition sequences described by finite automata are used for approximations to firing sequences, and the approximation error is assessed by Presburger expressions. The approximation algorithm is iterated until a sufficient criterion for reachability is satisfied. The exact computational complexity of the algorithm is an open problem.

UR - https://www.scopus.com/pages/publications/0021474508

U2 - 10.1137/0213029

DO - 10.1137/0213029

M3 - Article

AN - SCOPUS:0021474508

SN - 0097-5397

VL - 13

SP - 441

EP - 460

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

ALGORITHM FOR THE GENERAL PETRI NET REACHABILITY PROBLEM.

Abstract

Access to Document

Other files and links

Fingerprint

Cite this