{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:33:40Z","timestamp":1767929620534,"version":"3.49.0"},"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>We study the reachability problem for affine $\\mathbb{Z}$-VASS, which are\ninteger vector addition systems with states in which transitions perform affine\ntransformations on the counters. This problem is easily seen to be undecidable\nin general, and we therefore restrict ourselves to affine $\\mathbb{Z}$-VASS\nwith the finite-monoid property (afmp-$\\mathbb{Z}$-VASS). The latter have the\nproperty that the monoid generated by the matrices appearing in their affine\ntransformations is finite. The class of afmp-$\\mathbb{Z}$-VASS encompasses\nclassical operations of counter machines such as resets, permutations,\ntransfers and copies. We show that reachability in an afmp-$\\mathbb{Z}$-VASS\nreduces to reachability in a $\\mathbb{Z}$-VASS whose control-states grow\nlinearly in the size of the matrix monoid. Our construction shows that\nreachability relations of afmp-$\\mathbb{Z}$-VASS are semilinear, and in\nparticular enables us to show that reachability in $\\mathbb{Z}$-VASS with\ntransfers and $\\mathbb{Z}$-VASS with copies is PSPACE-complete. We then focus\non the reachability problem for affine $\\mathbb{Z}$-VASS with monogenic\nmonoids: (possibly infinite) matrix monoids generated by a single matrix. We\nshow that, in a particular case, the reachability problem is decidable for this\nclass, disproving a conjecture about affine $\\mathbb{Z}$-VASS with infinite\nmatrix monoids we raised in a preliminary version of this paper. We complement\nthis result by presenting an affine $\\mathbb{Z}$-VASS with monogenic matrix\nmonoid and undecidable reachability relation.<\/jats:p>","DOI":"10.46298\/lmcs-17(3:1)2021","type":"journal-article","created":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T09:55:34Z","timestamp":1627379734000},"source":"Crossref","is-referenced-by-count":3,"title":["Affine Extensions of Integer 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":[]},{"given":"Christoph","family":"Haase","sequence":"additional","affiliation":[]},{"given":"Filip","family":"Mazowiecki","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6660-5673","authenticated-orcid":false,"given":"Mikhail","family":"Raskin","sequence":"additional","affiliation":[]}],"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\/7686\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/7686\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:17:23Z","timestamp":1687292243000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/5797"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,20]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-17(3:1)2021","relation":{"has-preprint":[{"id-type":"arxiv","id":"1909.12386v2","asserted-by":"subject"},{"id-type":"arxiv","id":"1909.12386v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1909.12386","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1909.12386","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,20]]},"article-number":"5797"}}