{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:01Z","timestamp":1753894381304,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2021,7,20]],"date-time":"2021-07-20T00:00:00Z","timestamp":1626739200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["787367"],"award-info":[{"award-number":["787367"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Vector addition systems with states (VASS) are widely used for the formal\nverification of concurrent systems. Given their tremendous computational\ncomplexity, practical approaches have relied on techniques such as reachability\nrelaxations, e.g., allowing for negative intermediate counter values. It is\nnatural to question their feasibility for VASS enriched with primitives that\ntypically translate into undecidability. Spurred by this concern, we pinpoint\nthe complexity of integer relaxations with respect to arbitrary classes of\naffine operations.\n  More specifically, we provide a trichotomy on the complexity of integer\nreachability in VASS extended with affine operations (affine VASS). Namely, we\nshow that it is NP-complete for VASS with resets, PSPACE-complete for VASS with\n(pseudo-)transfers and VASS with (pseudo-)copies, and undecidable for any other\nclass. We further present a dichotomy for standard reachability in affine VASS:\nit is decidable for VASS with permutations, and undecidable for any other\nclass. This yields a complete and unified complexity landscape of reachability\nin affine VASS. We also consider the reachability problem parameterized by a\nfixed affine VASS, rather than a class, and we show that the complexity\nlandscape is arbitrary in this setting.<\/jats:p>","DOI":"10.46298\/lmcs-17(3:3)2021","type":"journal-article","created":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T09:55:53Z","timestamp":1627379753000},"source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Reachability in Affine Vector Addition Systems with States"],"prefix":"10.46298","volume":"Volume 17, Issue 3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2914-2734","authenticated-orcid":false,"given":"Michael","family":"Blondin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6660-5673","authenticated-orcid":false,"given":"Mikhail","family":"Raskin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2021,7,20]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/7687\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/7687\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:18:23Z","timestamp":1687292303000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/6872"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,20]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-17(3:3)2021","relation":{"has-preprint":[{"id-type":"arxiv","id":"1909.02579v4","asserted-by":"subject"},{"id-type":"arxiv","id":"1909.02579v3","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1909.02579","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1909.02579","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2021,7,20]]},"article-number":"6872"}}