×

Completeness results for conflict-free vector replacement systems. (English) Zbl 0661.68061

We give completeness results for the reachability, containment, and equivalence problems for conflict-free vector replacement systems (VRSs). We first give an NP algorithm for deciding reachability, thus giving the first primitive recursive algorithm for this problem. Since Jones, Landweber, and Lien have shown this problem to be NP-hard [N. D. Jones, L. H. Landweber and Y. E. Lien, Theor. Comput. Sci., 277-299 (1977; Zbl 0357.68048)], it follows that the problem is NP- complete. Next, we show as our main result that the containment and equivalence problems are \(\Pi^ p_ 2\)-complete, where \(\Pi^ p_ 2\) is the set of all languages whose complements are in the second level of the polynomial-time hierarchy. In showing the upper bound, we first show that the reachability set has a semilinear set (SLS) representation that is exponential in the size of the problem description, but which has a high degree of symmetry. We are then able to utilize in part a strategy introduced by Thiet-Dung Huynh [Electron. Informationsverarbeitung Kybernetik 18, 291-338 (1982; Zbl 0519.68060)] (concerning SLSs) to complete our upper bound proof.

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, H., Rabin’s Proof of the Undecidability of the Reachability Set Inclusion Problem of Vector Addition Systems (1973), MIT: MIT Cambridge, MA, Project MAC.CSGM 79
[2] Borosh, I.; Treybig, L., Bounds on positive integral solutions of linear Diophantine equations, Proc. Amer. Math. Soc., 55, No. 2, 299-304 (1976) · Zbl 0291.10014
[3] Cardoza, E.; Lipton, R.; Meyer, A., Exponential space complete problems for Petri nets and commutative semigroups, (Proceedings, 8th Annual ACM Symposium on Theory of Computing (1976)), 50-54 · Zbl 0374.20067
[4] Clots, P., The finite containment problem for Petri nets, Theoret. Comput. Sci., 43, 99-106 (1986)
[5] Crespi-Reghizzi, S.; Mandrioli, D., A decidability theorem for a class of vector addition systems, Inform. Process. Lett., 3, No. 3, 78-80 (1975) · Zbl 0302.68065
[6] Ginzburg, A.; Yoeli, M., Vector addition systems and regular languages, J. Comput. System Sci., 20, 277-284 (1980) · Zbl 0446.68043
[7] Grabowski, J., The decidability of persistence for vector addition systems, Inform. Process. Lett., 11, No. 1, 20-23 (1980) · Zbl 0444.68045
[8] Hack, M., The equality problem for vector addition systems is undecidable, Theoret. Comput. Sci., 2, 77-95 (1976) · Zbl 0357.68038
[9] Hopcroft, J.; Pansiot, J., On the reachability problem for 5-dimensional vector addition systems, Theoret. Comput. Sci., 8, 135-159 (1979) · Zbl 0466.68048
[10] Howell, R.; Rosier, L.; Huynh, D.; Yen, H., Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states, Theoret. Comput. Sci., 46, 107-140 (1986) · Zbl 0633.68029
[11] Howell, R.; Rosier, L.; Yen, H., An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems, Inform. Process. Lett., 25, 27-33 (1987) · Zbl 0634.68058
[12] Huynh, D., The complexity of semilinear sets, Electron. Informationsverarb. Kybernetik, 18, 291-338 (1982) · Zbl 0519.68060
[13] Huynh, D., The complexity of the equivalence problem for commutative semigroups and symmetric vector addition systems, (Proceedings, 17th Annual ACM Symposium on Theory of Computing (1985)), 405-412
[14] Huynh, D., A simple proof for the \(Σ_2^P\) upper bound of the inequivalence problem for semilinear sets, Elektron. Informationsverarb. Kybernet., 22, 147-156 (1986) · Zbl 0617.68050
[15] Jones, N.; Landweber, L.; Lien, Y., Complexity of some problems in Petri nets, Theoret. Comput. Sci., 4, 277-299 (1977) · Zbl 0357.68048
[16] Karp, R.; Miller, R., Parallel program schemata, J. Comput. System Sci., 3, No. 2, 147-195 (1969) · Zbl 0198.32603
[17] Kosaraju, R., Decidability of reachability in vector addition systems, (Proceedings, 14th Annual ACM Symposium on Theory of Computing (1982)), 267-280
[18] Landweber, L.; Robertson, E., Properties of conflict-free and persistent Petri nets, J. Assoc. Comput. Mach., 25, No. 3, 352-364 (1978) · Zbl 0384.68062
[19] Lipton, R., The Reachability Problem Requires Exponential Space (Jan. 1976), Yale University, Dept. of CS. Report No. 62
[20] Mayr, E.; Meyer, A., The complexity of the finite containment problem for Petri nets, J. Assoc. Comput. Mach., 28, No. 3, 561-576 (1981) · Zbl 0462.68020
[21] Mayr, E.; Meyer, A., The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. in Math., 46, 305-329 (1982) · Zbl 0506.03007
[22] Mayr, E., 13th Annual Symposium on Theory of Computing (1981), preliminary version
[23] Mayr, E., Persistence of vector replacement systems is decidable, Acta Inform., 15, 309-318 (1981) · Zbl 0454.68048
[24] McAloon, K., Petri nets and large finite sets, Theoret. Comput. Sci., 32, 173-183 (1984) · Zbl 0569.68046
[25] Muller, H., On the reachability problem for persistent vector replacement systems, Computing Suppl., 3, 89-104 (1981)
[26] Muller, H., Weak Petri net computers for Ackermann functions, Elektron. Informationsverarb. Kybernet., 21, 236-244 (1985)
[27] Rosier, L.; Yen, H., A multiparameter analysis of the boundedness problem for vector addition systems, J. Comput. System Sci., 32, No. 1, 105-135 (1986) · Zbl 0614.68048
[28] Stockmeyer, L., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[29] Stoer, J.; Witzgall, C., Convexity and Optimization in Finite Dimensions I (1970), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0203.52203
[30] Valk, R.; Viral-Naquet, G., Petri nets and regular languages, J. Comput. System Sci., 23, 299-325 (1981) · Zbl 0473.68057
[31] Von Zur Gathen, J.; Sieveking, M., A bound on solutions of linear integer equalities and inequalities, (Proc. Amer. Math. Soc., 72 (1978)), 155-158, No. 1 · Zbl 0397.90071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.