zbMATH — the first resource for mathematics

On the reachability problem for 5-dimensional vector addition systems. (English) Zbl 0466.68048

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
03B25 Decidability of theories and sets of sentences
03D80 Applications of computability and recursion theory
Full Text: DOI
[1] Baker, H.G., Rabin’s proof of the undecidability of the reachability set inclusion problem of vector addition systems, ()
[2] Cardoza, E.W., Computational complexity of the word problem for commutative semigroups, ()
[3] Ginsburg, S., The mathematical theory of context free languages, (1966), McGraw-Hill New York · Zbl 0184.28401
[4] Hack, M.H., The equality problem for vector addition systems is undecidable, () · Zbl 0357.68038
[5] Hack, M.H., Decision problems for Petri nets and vector addition systems, ()
[6] Holt, A.H., Final report of the information system theory project, ()
[7] Karp, R.M.; Miller, R.E., Parallel program schemata, J. comput. syst. sci., 3, 147-195, (1969) · Zbl 0198.32603
[8] Sacerdote, G.S.; Tenney, R.L., The decidability of the reachability problem for vector addition systems, Ninth ann. ACM symp. on theory of computing, 61-76, (1977)
[9] Van Leeuwen, J., A partial solution to the reachability problem for vector addition systems, Sixth ann. ACM symp. on the theory of computing, 303-309, (1974)
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.