Article

Free access

Decidability of reachability in vector addition systems (Preliminary Version)

Author:

S. Rao KosarajuAuthors Info & Claims

STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing

Pages 267 - 281

https://doi.org/10.1145/800070.802201

Published: 05 May 1982 Publication History

PDF eReader

Abstract

A convincing proof of the decidability of reachability in vector addition systems is presented. No drastically new ideas beyond those in Sacerdote and Tenney, and Mayr are made use of. The complicated tree constructions in the earlier proofs are completely eliminated.

References

[1]

Ginsburg, S.: The Mathematical Theory of Context-Free Languages, McGraw Hill Book Co., New York, 1966.

Digital Library

Google Scholar

[2]

Harary, F.: Graph Theory, Addison-Wesley Publishing Co., Reading, Mass., 1972.

Google Scholar

[3]

Hopcroft, J. and Pansiot, J.: On the reachability problem for 5-dimensional vector addition systems, Theoretical Computer Science, 135-159, 1979.

Crossref

Google Scholar

[4]

Mayr, E. W.: An algorithm for the general Petri Net Reachability Problem, Proc. of the 13th Annual ACM Symp. on Theory of Computing, 238-246, 1981.

Digital Library

Google Scholar

[5]

Sacerdote, G. S. and Tenney, R. L.: The decidability of the reachability problem for vector addition systems, Proc. of the 9th Annual ACM Symp. on Theory of Computing, 61-76, 1977.

Digital Library

Google Scholar

[6]

Sacerdote, G. S. and Tenney, R. L.: Vector Addition Systems, Tech. Report, October 1977.

Google Scholar

[7]

Van Leeuwen, J.: A partial solution to the reachability problem for vector-addition systems, Proc. of the 6th Annual ACM Symp. on Theory of Computing, 303-307, 1974.

Digital Library

Google Scholar

Cited By

View all

Anand ASchmitz SSchütze LZetzsche GSobocinski PLago UEsparza J(2024)Verifying Unboundedness via AmalgamationProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662133(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662133
Keskin EMeyer RSobocinski PLago UEsparza J(2024)On the Separability Problem of VASS Reachability LanguagesProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662116(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662116
Blondin MFinkel AHofman PMazowiecki FOfftermatt PSobocinski PLago UEsparza J(2024)Soundness of reset workflow netsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662086(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662086
Show More Cited By

Recommendations

Vector addition system reachability problem: a short self-contained proof
POPL '11: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

The reachability problem for Vector Addition Systems (VASs) is a central problem of net theory. The general problem is known decidable by algorithms exclusively based on the classical Kosaraju-Lambert-Mayr-Sacerdote-Tenney decomposition (KLMTS ...
The decidability of the reachability problem for vector addition systems (Preliminary Version)
STOC '77: Proceedings of the ninth annual ACM symposium on Theory of computing

Let V be a finite set of integral vectors in Euclidian N-space, and let a be an integral point in the first orthant of N-space. The reachability set R(a,V) is the set of integral points b in the first orthant such that there is a polygonal path γ from a ...
Binary Reachability of Timed-register Pushdown Automata and Branching Vector Addition Systems

Timed-register pushdown automata constitute a very expressive class of automata, whose transitions may involve state, input, and top-of-stack timed registers with unbounded differences. They strictly subsume pushdown timed automata of Bouajjani et al., ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing

May 1982

408 pages

ISBN:0897910702

DOI:10.1145/800070

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 May 1982

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

235
Total Citations
View Citations
278
Total Downloads

Downloads (Last 12 months)162
Downloads (Last 6 weeks)25

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Anand ASchmitz SSchütze LZetzsche GSobocinski PLago UEsparza J(2024)Verifying Unboundedness via AmalgamationProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662133(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662133
Keskin EMeyer RSobocinski PLago UEsparza J(2024)On the Separability Problem of VASS Reachability LanguagesProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662116(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662116
Blondin MFinkel AHofman PMazowiecki FOfftermatt PSobocinski PLago UEsparza J(2024)Soundness of reset workflow netsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662086(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662086
Ibarra OMcQuillan I(2024)On Decision Problems Concerning Contextual Insertions and DeletionsTheoretical Computer Science10.1016/j.tcs.2024.114905(114905)Online publication date: Oct-2024
https://doi.org/10.1016/j.tcs.2024.114905
Shabana AAlphy GSheerazuddin S(2024)Counter abstraction for regular open teamsInformation Processing Letters10.1016/j.ipl.2024.106533(106533)Online publication date: Sep-2024
https://doi.org/10.1016/j.ipl.2024.106533
Zhang LZhang Z(2024)Numerical P Systems with Thresholds and Petri NetsBio-Inspired Computing: Theories and Applications10.1007/978-981-97-2272-3_25(331-338)Online publication date: 16-Apr-2024
https://doi.org/10.1007/978-981-97-2272-3_25
Draghici AHaase CRyzhikov A(2024)Reachability in Fixed VASS: Expressiveness and Lower BoundsFoundations of Software Science and Computation Structures10.1007/978-3-031-57231-9_9(185-205)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57231-9_9
Leroux J(2024)Ackermannian Completion of SeparatorsFoundations of Software Science and Computation Structures10.1007/978-3-031-57228-9_1(3-10)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57228-9_1
Pratt-Hartmann IPratt-Hartmann I(2023)TreesFragments of First-Order Logic10.1093/oso/9780192867964.003.0015(600-629)Online publication date: 18-May-2023
https://doi.org/10.1093/oso/9780192867964.003.0015
Pratt-Hartmann IPratt-Hartmann I(2023)TransitivityFragments of First-Order Logic10.1093/oso/9780192867964.003.0014(544-599)Online publication date: 18-May-2023
https://doi.org/10.1093/oso/9780192867964.003.0014
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Vector addition system reachability problem: a short self-contained proof

The decidability of the reachability problem for vector addition systems (Preliminary Version)

Binary Reachability of Timed-register Pushdown Automata and Branching Vector Addition Systems