{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:57:51Z","timestamp":1742957871925,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031572302"},{"type":"electronic","value":"9783031572319"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T00:00:00Z","timestamp":1712361600000},"content-version":"vor","delay-in-days":96,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The recent years have seen remarkable progress in establishing the complexity of the reachability problem for vector addition systems with states (VASS), equivalently known as Petri nets. Existing work primarily considers the case in which both the VASS as well as the initial and target configurations are part of the input. In this paper, we investigate the reachability problem in the setting where the VASS and the final configuration are fixed and only the initial configuration is variable. We show that fixed VASS fully express arithmetic with counting on initial segments of the natural numbers. It follows that there is a very weak reduction from any fixed such number-theoretic predicate (e.g. square-freeness or \u201c<jats:inline-formula><jats:alternatives><jats:tex-math>$$N_1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the number of primes smaller than <jats:inline-formula><jats:alternatives><jats:tex-math>$$N_2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u201d) to reachability in fixed VASS where configurations are presented in unary. If configurations are given in binary, we show that there is a fixed VASS with five counters whose reachability problem is PSPACE-hard.<\/jats:p>","DOI":"10.1007\/978-3-031-57231-9_9","type":"book-chapter","created":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T18:01:54Z","timestamp":1712340114000},"page":"185-205","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Reachability in Fixed VASS: Expressiveness and Lower Bounds"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-9308-1169","authenticated-orcid":false,"given":"Andrei","family":"Draghici","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5452-936X","authenticated-orcid":false,"given":"Christoph","family":"Haase","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2031-2488","authenticated-orcid":false,"given":"Andrew","family":"Ryzhikov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,6]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. SIAM Journal on Computing 38(5), 1987\u20132006 (2009). https:\/\/doi.org\/10.1137\/070697926","DOI":"10.1137\/070697926"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity \u2013 A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC$$^1$$. Journal of Computer and System Sciences 41(3), 274\u2013306 (1990). https:\/\/doi.org\/10.1016\/0022-0000(90)90022-D","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Chistikov, D., Majumdar, R., Schepper, P.: Subcubic certificates for CFL reachability. Proceedings of the ACM on Programming Languages 6(POPL) (2022). https:\/\/doi.org\/10.1145\/3498702","DOI":"10.1145\/3498702"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Czerwi\u0144ski, W., Lasota, S., Lazi\u0107, R., Leroux, J., Mazowiecki, F.: The reachability problem for petri nets is not elementary. Journal of the ACM 68(1), 1\u201328 (2020). https:\/\/doi.org\/10.1145\/3313276.3316369","DOI":"10.1145\/3422822"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Czerwinski, W., Orlikowski, L.: Reachability in vector addition systems is Ackermann-complete. In: Annual Symposium on Foundations of Computer Science, FOCS. pp. 1229\u20131240. IEEE (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00120","DOI":"10.1109\/FOCS52979.2021.00120"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Czerwinski, W., Orlikowski, L.: Lower bounds for the reachability problem in fixed dimensional VASSes. In: Symposium on Logic in Computer Science, LICS. Association for Computing Machinery, New York, NY, USA (2022). https:\/\/doi.org\/10.1145\/3531130.3533357","DOI":"10.1145\/3531130.3533357"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of Bodlaender and Courcelle. In: Annual Symposium on Foundations of Computer Science, FOCS. pp. 143\u2013152 (2010). https:\/\/doi.org\/10.1109\/FOCS.2010.21","DOI":"10.1109\/FOCS.2010.21"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Esbelin, H.A., More, M.: Rudimentary relations and primitive recursion: A toolbox. Theoretical Computer Science 193(1), 129\u2013148 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00002-9","DOI":"10.1016\/S0304-3975(97)00002-9"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Fischer, P.C., Meyer, A.R., Rosenberg, A.L.: Counter machines and counter languages. Mathematical systems theory 2, 265\u2013283 (1968). https:\/\/doi.org\/10.1007\/BF01694011","DOI":"10.1007\/BF01694011"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Greibach, S.A.: The hardest context-free language. SIAM Journal on Computing 2(4), 304\u2013310 (1973). https:\/\/doi.org\/10.1137\/0202025","DOI":"10.1137\/0202025"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Greibach, S.A.: Remarks on the complexity of nondeterministic counter languages. Theoretical Computer Science 1(4), 269\u2013288 (1976). https:\/\/doi.org\/10.1016\/0304-3975(76)90072-4","DOI":"10.1016\/0304-3975(76)90072-4"},{"key":"9_CR13","unstructured":"Jecker, I.: 22.1 complexity of fixed vas reachability. https:\/\/autoboz.org\/open-problems (2023), accessed: 2023-10-12"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Kosaraju, S.R.: Decidability of reachability in vector addition systems (preliminary version). In: Symposium on Theory of Computing, STOC. pp. 267\u2013281. ACM (1982). https:\/\/doi.org\/10.1145\/800070.802201","DOI":"10.1145\/800070.802201"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Leroux, J.: The reachability problem for petri nets is not primitive recursive. In: Annual Symposium on Foundations of Computer Science, FOCS. pp. 1241\u20131252. IEEE (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00121","DOI":"10.1109\/FOCS52979.2021.00121"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Leroux, J., Schmitz, S.: Demystifying reachability in vector addition systems. In: Symposium on Logic in Computer Science, LICS. pp. 56\u201367. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/LICS.2015.16","DOI":"10.1109\/LICS.2015.16"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Leroux, J., Schmitz, S.: Reachability in vector addition systems is primitive-recursive in fixed dimension. In: Symposium on Logic in Computer Science (LICS). pp. 1\u201313 (2019). https:\/\/doi.org\/10.1109\/LICS.2019.8785796","DOI":"10.1109\/LICS.2019.8785796"},{"key":"9_CR18","unstructured":"Lipton, R.J.: The reachability problem requires exponential space. Research report (Yale University. Department of Computer Science), Department of Computer Science, Yale University (1976)"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Mayr, E.W.: An algorithm for the general petri net reachability problem. SIAM Journal on Computing 13(3), 441\u2013460 (1984). https:\/\/doi.org\/10.1137\/0213029","DOI":"10.1137\/0213029"},{"key":"9_CR20","unstructured":"Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall, USA (1967)"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Nguyen, D., Pak, I.: Short Presburger arithmetic is hard. SIAM Journal on Computing 51(2), 17:1\u201330 (2022). https:\/\/doi.org\/10.1137\/17M1151146","DOI":"10.1137\/17M1151146"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Rosier, L.E., Yen, H.C.: A multiparameter analysis of the boundedness problem for vector addition systems. Journal of Computer and System Sciences 32(1), 105\u2013135 (1986). https:\/\/doi.org\/10.1016\/0022-0000(86)90006-1","DOI":"10.1016\/0022-0000(86)90006-1"},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Rytter, W.: A hardest language recognized by two-way nondeterministic pushdown automata. Information Processing Letters 13(4), 145\u2013146 (1981). https:\/\/doi.org\/10.1016\/0020-0190(81)90045-4","DOI":"10.1016\/0020-0190(81)90045-4"},{"key":"9_CR24","unstructured":"Schroeppel, R.: A two counter machine cannot calculate $$2^N$$. Artificial Intelligence Memo 257, Massachusetts Institute of Technology (1972)"},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"Schweikardt, N.: Arithmetic, first-order logic, and counting quantifiers. ACM Transactions on Computational Logic (TOCL) 6(3), 634\u2013671 (2005). https:\/\/doi.org\/10.1145\/1071596.1071602","DOI":"10.1145\/1071596.1071602"},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages (extended abstract). In: Symposium on Theory of Computing, STOC. pp. 137\u2013146. Association for Computing Machinery, New York, NY, USA (1982). https:\/\/doi.org\/10.1145\/800070.802186","DOI":"10.1145\/800070.802186"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Weispfenning, V.: The complexity of almost linear diophantine problems. Journal of Symbolic Computation 10(5), 395\u2013403 (1990). https:\/\/doi.org\/10.1016\/S0747-7171(08)80051-X","DOI":"10.1016\/S0747-7171(08)80051-X"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-57231-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T16:04:24Z","timestamp":1714752264000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-57231-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031572302","9783031572319"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-57231-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"6 April 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 April 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2024\/conferences\/fossacs\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"79","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}