TY - JOUR
T1 - Complexity Results for Problems of Communication-Free Petri Nets and Related Formalisms
AU - Mayr, Ernst W.
AU - Weihmann, Jeremias
N1 - Publisher Copyright:
© 2015, ISO Press. All rights reserved.
PY - 2015
Y1 - 2015
N2 - We investigate several computational problems of communication-free Petri nets, and develop very efficient (mostly linear time) algorithms for different variations of the boundedness and liveness problems of cf-PNs. For several more complex notions of boundedness, as well as for the covering problem, we show NP-completeness. In the last part, we use our results for cf-PNs to give linear time algorithms for related problems of context-free (commutative) grammars, and, in turn, use known results for such grammars to give a coNEXPTIME-upper bound for the equivalence problem of cf-PNs.
AB - We investigate several computational problems of communication-free Petri nets, and develop very efficient (mostly linear time) algorithms for different variations of the boundedness and liveness problems of cf-PNs. For several more complex notions of boundedness, as well as for the covering problem, we show NP-completeness. In the last part, we use our results for cf-PNs to give linear time algorithms for related problems of context-free (commutative) grammars, and, in turn, use known results for such grammars to give a coNEXPTIME-upper bound for the equivalence problem of cf-PNs.
UR - http://www.scopus.com/inward/record.url?scp=84925712509&partnerID=8YFLogxK
U2 - 10.3233/FI-2015-1170
DO - 10.3233/FI-2015-1170
M3 - Article
AN - SCOPUS:84925712509
SN - 0169-2968
VL - 137
SP - 61
EP - 86
JO - Fundamenta Informaticae
JF - Fundamenta Informaticae
IS - 1
ER -