zbMATH — the first resource for mathematics

The covering and boundedness problems for vector addition systems. (English) Zbl 0368.68054

68Q25 Analysis of algorithms and problem complexity
68W99 Algorithms in computer science
Full Text: DOI
[1] Borosh, I.; Treybis, L., Bounds on positive integral solutions of linear Diophantine equations, Proc. AMS, 55, 199-304, (1976)
[2] Cardoza, E.; Lipton, R.J.; Meyer, A.R., Exponential space complete problems for Petri nets and commutative semigroups, 8th annual ACM symp. on theory of computing, 50-54, (1976) · Zbl 0374.20067
[3] Hack, M., The equality problem for vector addition systems is undecidable, Theor. comput. sci., 2, 77-96, (1976) · Zbl 0357.68038
[4] Karp, R.; Miller, R., Parallel program schemata, J. comput. system sci., 3, 147-195, (1969) · Zbl 0198.32603
[5] Lipton, R., The reachability problem requires exponential space, (), (to appear in Theoret. Comput. Sci.).
[6] Mayr, E., The complexity of the finite containment problem for Petri nets., () · Zbl 0462.68020
[7] Sacerdote, G.S.; Tenney, R.L., The decidability of the reachability problem for vector addition systems, 9th annual ACM symp. on theory of computing, 61-76, (1977)
[8] Savitch, W.J., Relation between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, (1970) · Zbl 0188.33502
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.