Complexity Results for Problems of Communication-Free Petri Nets and Related Formalisms
作者： Ernst W. Mayr , Jeremias Weihmann
DOI: 10.3233/FI-2015-1170
关键词:
摘要: We investigate several computational problems of communication-free Petri nets, and develop very efficient mostly linear time algorithms for different variations the boundedness liveness cf-PNs. For more complex notions boundedness, as well covering problem, we show NP-completeness. In last part, use our results cf-PNs to give related context-free commutative grammars, and, in turn, known such grammars a coNEXPTIME-upper bound equivalence problem
sci-hub.se 参考文章(33)
Peter Rossmanith, Stefan Schwoon, Javier Esparza, A Uniform Framework for Problems on Context-Free Grammars. Bulletin of The European Association for Theoretical Computer Science. ,vol. 72, pp. 169- 177 ,(2000)
Ernst W. Mayr, Jeremias Weihmann, Results on equivalence, boundedness, liveness, and covering problems of BPP-Petri nets applications and theory of petri nets. pp. 70- 89 ,(2013) , 10.1007/978-3-642-38697-8_5
Ernst W. Mayr, Jeremias Weihmann, Completeness Results for Generalized Communication-Free Petri Nets with Arbitrary Edge Multiplicities international workshop on reachability problems. pp. 209- 221 ,(2013) , 10.1007/978-3-642-41036-9_19
Richard Mayr, On the Complexity of Bisimulation Problems for Basic Parallel Processes international colloquium on automata languages and programming. pp. 329- 341 ,(2000) , 10.1007/3-540-45022-X_29
Robin Milner, Communication and Concurrency ,(1989)
Richard Mayr, Tableau Methods for PA-Processes theorem proving with analytic tableaux and related methods. pp. 276- 290 ,(1997) , 10.1007/BFB0027420
Loïc Pottier, Minimal solutions of linear diophantine systems: bounds and algorithms rewriting techniques and applications. pp. 162- 173 ,(1991) , 10.1007/3-540-53904-2_94
Yen Hsu-Chun, On reachability equivalence for BPP-nets Theoretical Computer Science. ,vol. 179, pp. 301- 317 ,(1997) , 10.1016/S0304-3975(96)00147-8
Javier Esparza, Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes Fundamenta Informaticae. ,vol. 31, pp. 13- 25 ,(1997) , 10.3233/FI-1997-3112
Antonín Kučera, Regularity is Decidable for Normed PA Processes in Polynomial Time foundations of software technology and theoretical computer science. pp. 111- 122 ,(1996) , 10.1007/3-540-62034-6_42