TY - GEN
T1 - A framework for classical Petri net problems
T2 - 35th International Conference on Application and Theory of Petri Nets and Concurrency, PETRI NETS 2014
AU - Mayr, Ernst W.
AU - Weihmann, Jeremias
PY - 2014
Y1 - 2014
N2 - We present a framework based on permutations of firing sequences and on canonical firing sequences to approach computational problems involving classes of Petri nets with arbitrary arc multiplicities. As an example of application, we use these techniques to obtain PSPACE-completeness for the reachability and the covering problems of conservative Petri nets, generalizing known results for ordinary 1-conservative Petri nets. We also prove PSPACE-completeness for the RecLFS and the liveness problems of conservative Petri nets, for which, in case of ordinary 1-conservative Petri nets, PSPACE-membership but no matching lower bound has been known. Last, we show PSPACE-completeness for the containment and equivalence problems of conservative Petri nets. PSPACE-hardness of the problems mentioned above still holds if they are restricted to ordinary 1-conservative Petri nets.
AB - We present a framework based on permutations of firing sequences and on canonical firing sequences to approach computational problems involving classes of Petri nets with arbitrary arc multiplicities. As an example of application, we use these techniques to obtain PSPACE-completeness for the reachability and the covering problems of conservative Petri nets, generalizing known results for ordinary 1-conservative Petri nets. We also prove PSPACE-completeness for the RecLFS and the liveness problems of conservative Petri nets, for which, in case of ordinary 1-conservative Petri nets, PSPACE-membership but no matching lower bound has been known. Last, we show PSPACE-completeness for the containment and equivalence problems of conservative Petri nets. PSPACE-hardness of the problems mentioned above still holds if they are restricted to ordinary 1-conservative Petri nets.
UR - http://www.scopus.com/inward/record.url?scp=84904125020&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-07734-5_17
DO - 10.1007/978-3-319-07734-5_17
M3 - Conference contribution
AN - SCOPUS:84904125020
SN - 9783319077338
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 314
EP - 333
BT - Application and Theory of Petri Nets and Concurrency - 35th International Conference, PETRI NETS 2014, Proceedings
PB - Springer Verlag
Y2 - 23 June 2014 through 27 June 2014
ER -