@article{Mayr:2015aa,
    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.},
    Author = {Mayr, Ernst W. and Weihmann, Jeremias},
    BookTitle = {Fundamenta Informaticae},
    Pages = {61--86},
    Publisher = {IOS Press},
    Title = {Complexity Results for Problems of Communication-Free Petri Nets and Related Formalisms},
    Volume = {137},
    Year = {2015},
    bdsk-url-1 = {https://doi.org/10.3233/FI-2015-1170},
    date-added = {2020-07-08 14:20:07 +0200},
    date-modified = {2020-07-08 14:20:07 +0200},
    m1 = {1},
    ty = {JOUR},
    doi = {10.3233/FI-2015-1170}
}

@article{Mayr:2015aa, 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.}, Author = {Mayr, Ernst W. and Weihmann, Jeremias}, BookTitle = {Fundamenta Informaticae}, Pages = {61--86}, Publisher = {IOS Press}, Title = {Complexity Results for Problems of Communication-Free Petri Nets and Related Formalisms}, Volume = {137}, Year = {2015}, bdsk-url-1 = {https://doi.org/10.3233/FI-2015-1170}, date-added = {2020-07-08 14:20:07 +0200}, date-modified = {2020-07-08 14:20:07 +0200}, m1 = {1}, ty = {JOUR}, doi = {10.3233/FI-2015-1170} }