{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T15:31:57Z","timestamp":1759332717895,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T00:00:00Z","timestamp":1594166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Fonds de recherche du Qu\u00e9bec \u00f0 Nature et technologies"},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["787367"],"award-info":[{"award-number":["787367"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,8]]},"DOI":"10.1145\/3373718.3394741","type":"proceedings-article","created":{"date-parts":[[2020,5,26]],"date-time":"2020-05-26T00:23:18Z","timestamp":1590452598000},"page":"224-236","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The Complexity of Reachability in Affine Vector Addition Systems with States"],"prefix":"10.1145","author":[{"given":"Michael","family":"Blondin","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Sherbrooke Sherbrooke, Qu\u00e9bec, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail","family":"Raskin","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen Munich, Bavaria, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90067-0"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40229-1_35"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105908"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3329995.3330003"},{"volume-title":"Proc. 29th International Conference on Concurrency Theory (CONCUR). 14:1--14:17","year":"2018","author":"Blondin Michael","key":"e_1_3_2_1_5_1"},{"key":"e_1_3_2_1_6_1","unstructured":"Michael Blondin Christoph Haase Filip Mazowiecki and Mikhail A. Raskin. 2019. Affine Extensions of Integer Vector Addition Systems with States. CoRR (2019). arXiv:1909.12386  Michael Blondin Christoph Haase Filip Mazowiecki and Mikhail A. Raskin. 2019. Affine Extensions of Integer Vector Addition Systems with States. CoRR (2019). arXiv:1909.12386"},{"volume-title":"Proc. 32nd Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 301--312","year":"2012","author":"Bonnet R\u00e9mi","key":"e_1_3_2_1_7_1"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2012013"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.06.017"},{"volume-title":"Proc. 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC). 24--33","year":"2019","author":"Czerwi\u00c5Dski Wojciech","key":"e_1_3_2_1_10_1"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646486.694620"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/646252.686157"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-016-0272-3"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_40"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_37"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36206-1_14"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2751290.2751292"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146681"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11439-2_9"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Monika Heiner David R. Gilbert and Robin Donaldson. 2008. Petri Nets for Systems and Synthetic Biology. In Formal Methods for Computational Systems Biology. 215--264. https:\/\/doi.org\/10.1007\/978-3-540-68894-5_7  Monika Heiner David R. Gilbert and Robin Donaldson. 2008. Petri Nets for Systems and Synthetic Biology. In Formal Methods for Computational Systems Biology. 215--264. https:\/\/doi.org\/10.1007\/978-3-540-68894-5_7","DOI":"10.1007\/978-3-540-68894-5_7"},{"key":"e_1_3_2_1_21_1","unstructured":"John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley.  John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46520-3_6"},{"key":"e_1_3_2_1_23_1","article-title":"A Widening Approach to Multithreaded Program Verification","volume":"36","author":"Kaiser Alexander","year":"2014","journal-title":"ACM Trans. on Prog. Languages and Systems"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802201"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90173-D"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"J\u00e9r\u00f4me Leroux. 2010. The General Vector Addition System Reachability Problem by Presburger Inductive Invariants. Logical Methods in Computer Science 6 3 (2010). https:\/\/doi.org\/10.2168\/LMCS-6(3:22)2010  J\u00e9r\u00f4me Leroux. 2010. The General Vector Addition System Reachability Problem by Presburger Inductive Invariants. Logical Methods in Computer Science 6 3 (2010). https:\/\/doi.org\/10.2168\/LMCS-6(3:22)2010","DOI":"10.2168\/LMCS-6(3:22)2010"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926421"},{"key":"e_1_3_2_1_28_1","unstructured":"J\u00e9r\u00f4me Leroux. 2012. Vector Addition Systems Reachability Problem (A Simpler Solution). In Turing-100 -- The Alan Turing Centenary. 214--228.  J\u00e9r\u00f4me Leroux. 2012. Vector Addition Systems Reachability Problem (A Simpler Solution). In Turing-100 -- The Alan Turing Centenary. 214--228."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.16"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785796"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802477"},{"key":"e_1_3_2_1_33_1","unstructured":"Julien Reichert. 2015. Reachability games with counters: decidability and algorithms. Ph.D. Dissertation. \u00c9cole normale sup\u00e9rieure de Cachan France.  Julien Reichert. 2015. Reachability games with counters: decidability and algorithms. Ph.D. Dissertation. \u00c9cole normale sup\u00e9rieure de Cachan France."},{"volume-title":"Proc. 9th Symposium on Theory of Computing (STOC). 61--76","author":"George","key":"e_1_3_2_1_34_1"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25543-5_7"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08860-1_35"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126698000043"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218843009002002"}],"event":{"name":"LICS '20: 35th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"],"location":"Saarbr\u00fccken Germany","acronym":"LICS '20"},"container-title":["Proceedings of the 35th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394741","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3373718.3394741","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:35Z","timestamp":1750197755000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394741"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,8]]},"references-count":37,"alternative-id":["10.1145\/3373718.3394741","10.1145\/3373718"],"URL":"https:\/\/doi.org\/10.1145\/3373718.3394741","relation":{},"subject":[],"published":{"date-parts":[[2020,7,8]]},"assertion":[{"value":"2020-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}