TY - GEN
T1 - Results on equivalence, boundedness, liveness, and covering problems of BPP-Petri nets
AU - Mayr, Ernst W.
AU - Weihmann, Jeremias
PY - 2013
Y1 - 2013
N2 - Yen proposed a construction for a semilinear representation of the reachability set of BPP-Petri nets which can be used to decide the equivalence problem of two BPP-PNs in doubly exponential time. We first address a gap in this construction which therefore does not always represent the reachability set. We propose a solution which is formulated in such a way that a large portion of Yen's construction and proof can be retained, preserving the size of the semilinear representation and the double exponential time bound (except for possibly larger values of some constants). In the second part of the paper, we propose very efficient algorithms for several variations of the boundedness and liveness problems of BPP-PNs. For several more complex notions of boundedness, as well as for the covering problem, we show NP-completeness. To demonstrate the contrast between BPP-PNs and a slight generalization regarding edge multiplicities, we show that the complexity of the classical boundedness problem increases from linear time to coNP-hardness. Our results also imply corresponding complexity bounds for related problems for process algebras and (commutative) context-free grammars.
AB - Yen proposed a construction for a semilinear representation of the reachability set of BPP-Petri nets which can be used to decide the equivalence problem of two BPP-PNs in doubly exponential time. We first address a gap in this construction which therefore does not always represent the reachability set. We propose a solution which is formulated in such a way that a large portion of Yen's construction and proof can be retained, preserving the size of the semilinear representation and the double exponential time bound (except for possibly larger values of some constants). In the second part of the paper, we propose very efficient algorithms for several variations of the boundedness and liveness problems of BPP-PNs. For several more complex notions of boundedness, as well as for the covering problem, we show NP-completeness. To demonstrate the contrast between BPP-PNs and a slight generalization regarding edge multiplicities, we show that the complexity of the classical boundedness problem increases from linear time to coNP-hardness. Our results also imply corresponding complexity bounds for related problems for process algebras and (commutative) context-free grammars.
UR - http://www.scopus.com/inward/record.url?scp=84879648483&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38697-8_5
DO - 10.1007/978-3-642-38697-8_5
M3 - Conference contribution
AN - SCOPUS:84879648483
SN - 9783642386961
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 70
EP - 89
BT - Application and Theory of Petri Nets and Concurrency - 34th International Conference, PETRI NETS 2013, Proceedings
T2 - 34th International Conference on Application and Theory of Petri Nets and Concurrency, PETRI NETS 2013
Y2 - 24 June 2013 through 28 June 2013
ER -