Complexity Results for Problems of Communication-Free Petri Nets and Related Formalisms

Issue title: Application and Theory of Petri Nets and Concurrency. PETRI NETS 2013

Article type: Research Article

Authors: Mayr, Ernst W. | Weihmann, Jeremias

Affiliations: Institut für Informatik, Technische Universität München, Garching, Germany. mayr@in.tum.de; weihmann@in.tum.de

Note: [] Address for correspondence: Institut für Informatik, Technische Universität München, Boltzmannstr. 3, 85748 Garching, Germany

Abstract: 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.

DOI: 10.3233/FI-2015-1170

Journal: Fundamenta Informaticae, vol. 137, no. 1, pp. 61-86, 2015