TY - GEN
T1 - Completeness results for generalized communication-free Petri nets with arbitrary edge multiplicities
AU - Mayr, Ernst W.
AU - Weihmann, Jeremias
PY - 2013
Y1 - 2013
N2 - We investigate gcf-Petri nets, a generalization of communication-free Petri nets allowing arbitrary edge multiplicities, and characterized by the sole restriction that each transition has at most one incoming edge. We use canonical firing sequences with nice properties for gcf-PNs to show that the RecLFS, (zero-)reachability, covering, and boundedness problems of gcf-PNs are in PSPACE. By showing, how PSPACE-Turing machines can be simulated by gss-PNs, a subclass of gcf-PNs where additionally all transitions have at most one outgoing edge, we ultimately prove the PSPACE-completess of these problems for gss/gcf-PNs. Last, we show PSPACE-hardness as well as a doubly exponential space bound for the containment and equivalence problems of gss/gcf-PNs.
AB - We investigate gcf-Petri nets, a generalization of communication-free Petri nets allowing arbitrary edge multiplicities, and characterized by the sole restriction that each transition has at most one incoming edge. We use canonical firing sequences with nice properties for gcf-PNs to show that the RecLFS, (zero-)reachability, covering, and boundedness problems of gcf-PNs are in PSPACE. By showing, how PSPACE-Turing machines can be simulated by gss-PNs, a subclass of gcf-PNs where additionally all transitions have at most one outgoing edge, we ultimately prove the PSPACE-completess of these problems for gss/gcf-PNs. Last, we show PSPACE-hardness as well as a doubly exponential space bound for the containment and equivalence problems of gss/gcf-PNs.
UR - http://www.scopus.com/inward/record.url?scp=84886407203&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-41036-9_19
DO - 10.1007/978-3-642-41036-9_19
M3 - Conference contribution
AN - SCOPUS:84886407203
SN - 9783642410352
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 209
EP - 221
BT - Reachability Problems - 7th International Workshop, RP 2013, Proceedings
PB - Springer Verlag
T2 - 7th International Workshop on Reachability Problems, RP 2013
Y2 - 24 September 2013 through 26 September 2013
ER -