An Algorithm for the General Petri Net Reachability Problem
Author:
- Ernst W. MayrEMErnst W. Mayr
- 1 August 1984
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 13 (3) , 441-460
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 our algorithm is an open problem.Keywords
This publication has 21 references indexed in Scilit:
- The decidability of persistence for vector addition systemsInformation Processing Letters, 1980
- Proving termination with multiset orderingsCommunications of the ACM, 1979
- On the reachability problem for 5-dimensional vector addition systemsTheoretical Computer Science, 1979
- Remarks on blind and partially blind one-way multicounter machinesTheoretical Computer Science, 1978
- Complexity of some problems in Petri netsTheoretical Computer Science, 1977
- Petri nets and szilard languagesInformation and Control, 1977
- Decidable problems on the strong connectivity of Petri net reachability setsTheoretical Computer Science, 1977
- Reduction of Petri-netsLecture Notes in Computer Science, 1976
- Semigroups, Presburger formulas, and languagesPacific Journal of Mathematics, 1966
- Finiteness of the Odd Perfect and Primitive Abundant Numbers with n Distinct Prime FactorsAmerican Journal of Mathematics, 1913