Completeness Results for Generalized Communication-free Petri Nets with Arbitrary Arc Multiplicities

• Autorzy: Mayr E. W. , Weihmann J.

Identyfikatory

DOI

10.3233/FI-2016-1318

• Języki publikacji: EN

Abstrakty

EN

We investigate gcf-Petri nets, a generalization of communication-free Petri nets allowing arbitrary arc multiplicities, and characterized by the sole restriction that each transition has at most one incoming arc. We use canonical firing sequences with nice properties for gcf-PNs to show that the RecLFS, (zero-)reachability, covering, and boundedness problems of gcf-PNs are in PSPACE. By simulating PSPACE-Turing machines by gss-PNs, a subclass of gcf-PNs where additionally all transitions have at most one outgoing arc, we ultimately obtain PSPACE-completess for these problems in case of gss-PNs or gcf-PNs. Additionally, we prove PSPACE-completeness for the liveness problem of gcf-PNs. Last, we show PSPACE-hardness as well as a doubly exponential space upper bound for the containment and equivalence problems of gss-PNs or gcf-PNs.

Słowa kluczowe

EN

generalized communication-free Petri nets; join-free Petri nets; generalized S-systems; weighted state machines; arbitrary arc multiplicities; arbitrary edge multiplicities; general arc multiplicities; general edge multiplicities; generalized Petri nets; general Petri nets; reachability; boundedness; covering; liveness; equivalence; containment

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 143, nr 3/4
• Strony: 355--391
• Opis fizyczny: Bibliogr. 36 poz., rys., tab.

Twórcy

autor

Mayr E. W.

• Institut für Informatik, Technische Universität München, Garching, Germany

autor

Weihmann J.

• Institut für Informatik Technische, Universität München, Garching, Germany

Bibliografia

• [1] Mayr EW. An Algorithm for the General Petri Net Reachability Problem. SIAM Journal on Computing. 1984;13(3):441–460. Available from: http://epubs.siam.org/doi/abs/10.1137/0213029. doi:10.1137/0213029.
• [2] Esparza J. Petri nets, commutative context-free grammars, and basic parallel processes. Fundamenta Informaticae. 1997;31(1):13–25. Available from: http://iospress.metapress.com/content/k358666657p63035/. doi:10.3233/FI-1997-3112.
• [3] Yen HC. On reachability equivalence for BPP-nets. Theoretical Computer Science. 1997;179:301–317. Available from: http://www.sciencedirect.com/science/article/pii/ S0304397596001478. doi:10.1016/S0304-3975(96)00147-8.
• [4] Howell RR, Rosier LE. Completeness results for conflict-free vector replacement systems. Journal of Computer and System Sciences. 1988;37(3):349–366. Available from: http://www.sciencedirect.com/science/article/pii/002200008890013X. doi:10.1016/0022-0000(88)90013-X.
• [5] Howell RR, Rosier LE, Yen HC. Normal and sinkless Petri nets. In: Proceedings of the 1989 International Conference on Fundamentals of Computation Theory (FCT’89). vol. 380 of Lecture Notes in Computer Science. Springer; 1989. p. 234–243. doi:10.1007/3-540-51498-8_22.
• [6] Howell RR, Jancar P, Rosier LE. Completeness Results for Single-Path Petri Nets. Information and Computation. 1993;106(2):253–265. Available from: http://www.sciencedirect.com/science/article/pii/S0890540183710552. doi:10.1006/inco.1993.1055.
• [7] Mayr EW, Meyer AR. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics. 1982;46(3):305–329. Available from: http://www.sciencedirect.com/science/article/pii/0001870882900482. doi:10.1016/0001-8708(82)90048-2.
• [8] Cardoza E, Lipton R, Meyer AR. Exponential space complete problems for Petri nets and commutative semigroups (Preliminary Report). In: Proceedings of the 8th ACM Symposium on Theory of Computing (STOC’76). ACM; 1976. p. 50–54. Available from: http://doi.acm.org/10.1145/800113.803630. doi:10.1145/800113.803630.
• [9] Hiraishi K, Ichikawa A. A Class of Petri Nets that a Necessary and Sufficient Condition for Reachability is Obtainable. Transactions of the Society of Instrument and Control Engineers. 1988; 24(6):635–40.
• [10] Murata T. Petri nets: Properties, analysis and applications. Proceedings of the IEEE. 1989;77(4): 541–580. doi:10.1109/5.24143.
• [11] Stewart IA. On the reachability problem for some classes of Petri nets. Newcastle upon Tyne: Newcastle University; 1991. 357. Available from: http://www.cs.ncl.ac.uk/publications/trs/papers/357.pdf.
• [12] Esparza J, Nielsen M. Decibility Issues for Petri Nets - a survey. Journal of Information Processing and Cybernetics. 1994;30(3):143–160.
• [13] Christensen S. Distributed bisimularity is decidable for a class of infinite state-space systems. In: Proceedings of the 3rd International Conference on Concurrency Theory (CONCUR’92). vol. 630 of Lecture Notes in Computer Science. Springer; 1992. p. 148–161. doi:10.1007/BFb0084789.
• [14] Christensen S, Hirshfeld Y, Moller F. Bisimulation equivalence is decidable for basic parallel processes. In: Proceedings of the 4th International Conference on Concurrency Theory (CONCUR’93). vol. 715 of Lecture Notes in Computer Science. Springer; 1993. p. 143–157. doi:10.1007/3-540-57208-2_11.
• [15] Huynh DT. Commutative grammars: The complexity of uniform word problems. Information and Control. 1983;57(1):21–39. Available from: http://www.sciencedirect.com/science/article/ pii/S0019995883800229. doi:10.1016/S0019-9958(83)80022-9.
• [16] Holt AW, Commoner F. Events and conditions. In: Record of the Project MAC Conference on Concurrent Systems and Parallel Computation. New York: ACM; 1970. p. 3–52.
• [17] Lien YE. Termination Properties of Generalized Petri Nets. SIAM Journal on Computing. 1976;5(2):251–265. Available from: http://epubs.siam.org/doi/abs/10.1137/0205020. doi:10.1137/0205020.
• [18] Teruel E, Silva M. Liveness and home states in equal conflict systems. In: Proceedings of the 14th International Conference on Application and Theory of Petri Nets (ICATPN’93). vol. 691 of Lecture Notes in Computer Science. Springer; 1993. p. 415–432. Available from: http://dx.doi.org/10.1007/3-540-56863-8\_59. doi:10.1007/3-540-56863-8_59.
• [19] Teruel E, Silva M. Well-formedness of Equal Conflict systems. In: Proceedings of the 15th International Conference on Application and Theory of Petri Nets (ICATPN’94). vol. 815 of Lecture Notes in Computer Science. Springer; 1994. p. 491–510. Available from: http://dx.doi.org/10.1007/3-540-58152-9\_27. doi:10.1007/3-540-58152-9_27.
• [20] Teruel E, Silva M. Structure theory of equal conflict systems. Theoretical Computer Science. 1996;153:271–300. Available from: http://www.sciencedirect.com/science/article/pii/0304397595001247. doi:10.1016/0304-3975(95)00124-7.
• [21] Amer-Yahia C, Zerhouni N, Moudni AE, Ferney M. Some subclasses of Petri nets and the analysis of their structural properties: a new approach. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans. 1999;29(2):164–172. doi:10.1109/3468.747851.
• [22] Delosme JM, Hujsa T, Munier-Kordon A. Polynomial Sufficient Conditions of Well-Behavedness for Weighted Join-Free and Choice-Free Systems. In: Proceedings of the 13th International Conference on Application of Concurrency to System Design (ACSD’13); 2013. p. 90–99. doi:10.1109/ACSD.2013.12.
• [23] Morita K, Watanabe T. The legal firing sequence problem of Petri nets with state machine structure. In: Proceedings of the 1996 IEEE International Symposium on Circuits and Systems (ISCAS’96). vol. 3; 1996. p. 64–67. doi:10.1109/ISCAS.1996.541481.
• [24] Taoka S, Watanabe T. Time Complexity Analysis of the Legal Firing Sequence Problem of Petri Nets with Inhibitor Arcs. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2006;E89(11):3216–3226. doi:10.1093/ietfec/e89-a.11.3216.
• [25] Taoka S, Watanabe T. A linear time algorithm solving the legal firing sequence problem for a class of edge-weighted cactuses. In: Proceedings of the 1999 IEEE International Conference on Systems, Man, and Cybernetics (SMC’99). vol. 3; 1999. p. 893–898. doi:10.1109/ICSMC.1999.823346.
• [26] Ha LM, Trung PV, Duong PTH. A Polynomial-Time Algorithm for Reachability Problem of a Subclass of Petri Net and Chip Firing Games. In: Proceedings of the 2012 IEEE International Conference on Computing and Communication Technologies, Research, Innovation, and Vision for the Future (RIVF’12); 2012. p. 1–6. doi:10.1109/rivf.2012.6169852.
• [27] Mayr EW, Weihmann J. Results on Equivalence, Boundedness, Liveness, and Covering Problems of BPP-Petri Nets. In: Proceedings of the 34th International Conference on Application and Theory of Petri Nets (ICATPN’13). vol. 7927 of Lecture Notes in Computer Science. Springer; 2013. p. 70–89. Available from: http://dx.doi.org/10.1007/978-3-642-38697-8_5. doi:10.1007/978-3-642-38697-8_5.
• [28] Mayr EW, Weihmann J. Results for Problems of Communication-Free Petri Nets and Related Formalisms. Fundamenta Informaticae. 2015;137. To appear.
• [29] Huynh DT. The complexity of equivalence problems for commutative grammars. Information and Control. 1985;66(1–2):103–121. Available from: http://www.sciencedirect.com/science/article/pii/S0019995885800152. doi:10.1016/S0019-9958(85)80015-2.
• [30] Yen HC; 2013. Private Communication.
• [31] Jones ND, Landweber LH, Lien YE. Complexity of some problems in Petri nets. Theoretical Computer Science. 1977;4(3):277–299. Available from: http://www.sciencedirect.com/science/article/pii/0304397577900147. doi:10.1016/0304-3975(77)90014-7.
• [32] Pottier L. Minimal solutions of linear diophantine systems: bounds and algorithms. In: Proceedings of the 4th International Conference on Rewriting Techniques and Applications (RTA’91). vol. 488 of Lecture Notes in Computer Science. Springer; 1991. p. 162–173. Available from: http://dx. doi.org/10.1007/3-540-53904-2\_94. doi:10.1007/3-540-53904-2_94.
• [33] Immerman N. Nondeterministic Space is Closed under Complementation. SIAM Journal on Computing. 1988;17(5):935–938. Available from: http://epubs.siam.org/doi/abs/10.1137/0217058. doi:10.1137/0217058.
• [34] Szelepcsényi R. The method of forced enumeration for nondeterministic automata. Acta Informatica. 1988;26(3):279–284. Available from: http://dx.doi.org/10.1007/BF00299636. doi:10.1007/BF00299636.
• [35] Huynh DT. The complexity of semilinear sets. In: Proceedings of the 7th International Colloquium on Automata, Languages and Programming (ICALP’80). vol. 85 of Lecture Notes in Computer Science. Springer; 1980. p. 324–337. doi:10.1007/3-540-10003-2_81.
• [36] Huynh DT. A Simple Proof for the Σp2 Upper Bound of the Inequivalence Problem for Semilinear Sets. Elektronische Informationsverarbeitung und Kybernetik. 1986;22:147–156.