zbMATH — the first resource for mathematics

A multiparameter analysis of the boundedness problem for vector addition systems. (English) Zbl 0614.68048
The authors give a careful analysis of the complexity of the boundedness problem (BP; ”is the reachability set infinite?”) for vector addition systems (VAS) and vector addition systems with states (VASS), which are known to be equivalent to Petri nets. Upper and lower bounds for the complexity are given in dependence of three parameters: k: dimension of vectors, l: maximal bit length of vector components, n: number of states. The BP for such VASS(k,l,n) can be solved in \(O((l+\log n)*2^{c*k*\log k})\) nondeterministic space for some constant c (an improvement of Rackoff’s result). Lipton’s lower bound is improved to \(O((l+\log n)*2^{c*k})\). Furthermore, some complexity results for fixed small k and connections to nets of communicating finite state machines (CFSM) are given.
Reviewer: H.Müller

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Agerwala, T.; Flynn, M., Comments on capabilities, limitations, and correctness of Petri nets, (), 81-86
[2] Borosh, I.; Treybis, L., Bounds on positive integral solutions of linear Diophantine equations, (), 299-304 · Zbl 0291.10014
[3] Cook, S., Characterizations of pushdown machines in terms of time bounded computers, J. assoc. comput. Mach., 18, 4-18, (1971) · Zbl 0222.02035
[4] Cunha, P.; Maibaum, T., A synchronous calculus for message oriented programming, (), 443-445
[5] Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[6] Gouda, M.; Gurari, E.; Lai, T.; Rosier, L., Deadlock detection in systems of communicating finite state machines, () · Zbl 0639.68009
[7] Gouda, M.; Rosier, L., Priority networks of communicating finite state machines, SIAM J. comput., 14, 569-584, (1985) · Zbl 0563.68021
[8] Gurari, E.; Lai, T., Deadlock detection in communicating finite state machines, ACM SIGACT news, 15, No. 4, 63-64, (Winter-Spring 1984), 16, No. 4
[9] Hack, M., Decidability questions for Petri nets, Mit, lcs, tr. 161, (June 1976)
[10] Hopcroft, J.; Pansiot, J., On the reachability problem for 5-dimensional vector addition systems, Theoret. comput. sci., 8, 135-159, (1979) · Zbl 0466.68048
[11] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, Mass · Zbl 0426.68001
[12] Jones, N.; Landweber, L.; Lien, Y., Complexity of some problems in Petri nets, Theoret. comput. sci., 8, 277-299, (1979) · Zbl 0357.68048
[13] Kasai, T.; Iwata, S., Gradually intractable problems and nondeterministic logspace lower bounds, Math. systems theory, 18, 153-170, (1985) · Zbl 0578.68039
[14] Karp, R.; Miller, R., Parallel program schemata, J. comput. system sci., 3, 147-195, (1969) · Zbl 0198.32603
[15] Kosaraju, S., Limitations of Dijkstra’s semaphore primitives and Petri nets, Operating systems rev., 7, 122-126, (1973)
[16] Lawler, E., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart & Winston New York · Zbl 0413.90040
[17] Lipton, R., The reachability problem requires exponential space, Yale university, department of computer sciences, report no. 62, (Jan. 1976)
[18] Mayr, E.; Meyer, A., The complexity of the world problems for commutative semigroups and polynomial ideals, Adv. in math., 46, 305-329, (1982) · Zbl 0506.03007
[19] Minsky, M., Computation: finite and infinite machines, (1967), Prentice-Hall Englewood Cliffs, N. J · Zbl 0195.02402
[20] Parnas, D., On a solution to the cigarette Smoker’s problem (without conditional statements), Comm. ACM, 18, 181-183, (1975)
[21] Patil, S., Limitations and capabilities of Dijkstra’s semaphore primitives for coordination among processes, ()
[22] Peterson, J., Petri net theory and the modeling of systems, (1981), Prentice-Hall Englewood Cliffs, N. J
[23] Rackoff, C., The covering and boundedness problems for vector addition systems, Theoret. comput. sci., 6, 223-231, (1978) · Zbl 0368.68054
[24] Rosier, L.; Gouda, M., On deciding progress for a class of communication protocols, (), 663-667
[25] Rosier, L.; Yen, H., Boundedness, empty channel detection and synchronization for communicating finite state machines, (), 287-298
[26] Savitch, W., Relationships between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, 177-192, (1970) · Zbl 0188.33502
[27] Yu, Y.; Gouda, M., Unboundedness detection for a class of communicating finite state machines, Inform. process. lett., 17, 235-240, (1983) · Zbl 0519.68067
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.