Results on equivalence, boundedness, liveness, and covering problems of BPP-Petri nets

Ernst W. Mayr, Jeremias Weihmann

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

5 Zitate (Scopus)

Abstract

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.

OriginalspracheEnglisch
TitelApplication and Theory of Petri Nets and Concurrency - 34th International Conference, PETRI NETS 2013, Proceedings
Seiten70-89
Seitenumfang20
DOIs
PublikationsstatusVeröffentlicht - 2013
Veranstaltung34th International Conference on Application and Theory of Petri Nets and Concurrency, PETRI NETS 2013 - Milan, Italien
Dauer: 24 Juni 201328 Juni 2013

Publikationsreihe

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band7927 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

Konferenz

Konferenz34th International Conference on Application and Theory of Petri Nets and Concurrency, PETRI NETS 2013
Land/GebietItalien
OrtMilan
Zeitraum24/06/1328/06/13

Fingerprint

Untersuchen Sie die Forschungsthemen von „Results on equivalence, boundedness, liveness, and covering problems of BPP-Petri nets“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren