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

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

Identyfikatory

DOI

10.3233/FI-2015-1170

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

formal sociology; Petri nets; graph grammars; algorithms; linear models

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 137, nr 1
• Strony: 61--86
• Opis fizyczny: Bibliogr. 36 poz., rys.

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] Alimonti, P., Feuerstein, E., Nanni, U.: Linear time algorithms for liveness and boundedness in conflict-free Petri nets, in: Proceedings of the 1st Latin American Symposium on Theoretical Informatics (LATIN’92), vol. 583 of Lecture Notes in Computer Science, Springer, 1992, 1–14.
• [2] Arnold, A., Crubille, P.: A linear algorithm to solve fixed-point equations on transition systems, Information Processing Letters, 29(2), 1988, 57–66.
• [3] Chen, C.-L., Wang, S., Yen, H.-C.: Reachability analysis of variants of communication-free Petri nets., IEICE Transactions on Information and Systems, 92(3), 2009, 377–388.
• [4] 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, 148–161.
• [5] 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, 143–157.
• [6] Crespi-Reghizzi, S., Mandrioli, D.: Commutative grammars, CALCOLO, 13(2), 1976, 173–189.
• [7] Dickson, L. E.: Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors, American Journal of Mathematics, 35(4), 1913, 413–422.
• [8] Dowling, W. F., Gallier, J. H.: Linear-time algorithms for testing the satisfiability of propositional horn formulae, The Journal of Logic Programming, 1(3), 1984, 267–284.
• [9] Esparza, J.: Petri nets, commutative context-free grammars, and basic parallel processes, Fundamenta Informaticae, 31(1), 1997, 13–25.
• [10] Esparza, J., Rossmanith, P., Schwoon, S.: A uniform framework for problems on context-free grammars, Bulletin of the EATCS, 72, 2000, 169–177.
• [11] Fribourg, L., Olsén, H.: A decompositional approach for computing least fixed-points of datalog programs with z-counters, Constraints, 2(3-4), 1997, 305–335.
• [12] Hack, M.: The recursive equivalence of the reachability problem and the liveness problem for Petri nets and vector addition systems, IEEE Conference Record of the 15th Annual Symposium on Switching and Automata Theory, 1974.
• [13] Hirshfeld, Y.: Petri nets and the equivalence problem, in: Selected Papers of the 7th Workshop on Computer Science Logic (CSL’93), vol. 832 of Lecture Notes in Computer Science, Springer, 1994, 165–174.
• [14] Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
• [15] Howell, R. R., Rosier, L. E.: Completeness results for conflict-free vector replacement systems, Journal of Computer and System Sciences, 37(3), 1988, 349–366.
• [16] Howell, R. R., Rosier, L. E., Yen, H.-C.: An O(n1.5) algorithm to decide boundedness for conflictfree vector replacement systems, Information Processing Letters, 25(1), 1987, 27–33.
• [17] Huynh, D. T.: Commutative grammars: The complexity of uniform word problems, Information and Control, 57(1), 1983, 21–39.
• [18] Huynh, D. T.: The complexity of equivalence problems for commutative grammars, Information and Control, 66(1–2), 1985, 103–121.
• [19] Jones, N. D., Landweber, L. H., Lien, Y. E.: Complexity of some problems in Petri nets, Theoretical Computer Science, 4(3), 1977, 277–299.
• [20] Karp, R. M., Miller, R. E.: Parallel program schemata, Journal of Computer and System Sciences, 3(2), 1969, 147–195.
• [21] Kopczyński, E., To, A.W.: Parikh images of grammars: Complexity and applications, Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science (LICS), July 2010.
• [22] Kučera, A.: Regularity is decidable for normed PA processes in polynomial time, in: Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, vol. 1180 of Lecture Notes in Computer Science, Springer, 1996, 111–122.
• [23] Landweber, L. H., Robertson, E. L.: Properties of conflict-free and persistent Petri nets, Journal of the ACM, 25(3), 1978, 352–364.
• [24] Mayr, E. W.: An algorithm for the general Petri net reachability problem, Proceedings of the 13th ACM Symposium on Theory of Computing (STOC’81), ACM, 1981.
• [25] Mayr, E. W., Weihmann, J.: Completeness results for generalized communication-free Petri nets with arbitrary edge multiplicities, in: Proceedings of the 7th International Workshop on Reachability Problems, vol. 8169 of Lecture Notes in Computer Science, Springer, 2013, 209–221.
• [26] Mayr, E.W.,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, 70–89.
• [27] Mayr, R.: Tableau methods for PA-processes, in: Proceedings of the 1997 International Conference on Automated Reasoning with Analytic Tableaux and Related Methods (TABLEAUX’97), vol. 1227 of Lecture Notes in Computer Science, Springer, 1997, 276–290.
• [28] Mayr, R.: Decidability and Complexity of Model Checking Problems for Infinite-State Systems, Ph.D. Thesis, Technische UniversitÃd’t MÃijnchen, 1998.
• [29] Mayr, R.: On the complexity of bisimulation problems for basic parallel processes, in: Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP’00), vol. 1853 of Lecture Notes in Computer Science, Springer, 2000, 329–341.
• [30] Milner, R.: Communication and concurrency, Prentice Hall, 1995.
• [31] Murata, T.: Petri nets: Properties, analysis and applications, Proceedings of the IEEE, 77(4), 1989, 541–580.
• [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, 162–173.
• [33] Sippu, S., Soisalon-Soininen, E.: Parsing Theory, vol. 15 of EATCS Monographs on Theoretical Computer Science, Springer, 1988.
• [34] Tarjan, R.: Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1(2), 1972, 146–160.
• [35] Yen, H.-C.: On reachability equivalence for BPP-nets, Theoretical Computer Science, 179, 1997, 301–317.
• [36] Yen, H.-C.: Private Communication, 2013.