{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T00:35:37Z","timestamp":1776472537089,"version":"3.51.2"},"reference-count":58,"publisher":"IEEE","license":[{"start":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T00:00:00Z","timestamp":1559347200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T00:00:00Z","timestamp":1559347200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T00:00:00Z","timestamp":1559347200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1109\/lics.2019.8785850","type":"proceedings-article","created":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T01:15:55Z","timestamp":1565054155000},"page":"1-14","source":"Crossref","is-referenced-by-count":9,"title":["Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests"],"prefix":"10.1109","author":[{"given":"Christoph","family":"Haase","sequence":"first","affiliation":[]},{"given":"Georg","family":"Zetzsche","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"ref39","author":"lipton","year":"1976","journal-title":"The reachability problem requires exponential space"},{"key":"ref38","first-page":"80","article-title":"Parikh Images of Grammars: Complexity and Applications","author":"kopczy?ski","year":"2010","journal-title":"Logic in Computer Science LICS"},{"key":"ref33","first-page":"1045","article-title":"The virtual Haken conjecture. With an appendix by Agol, Daniel Groves, and Jason Manning","volume":"18","author":"agol","year":"2013","journal-title":"Doc Math"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005065"},{"key":"ref31","first-page":"24:1","article-title":"Linear Equations with Ordered Data","volume":"118","author":"hofman","year":"2018","journal-title":"CONCUR 98 Concurrency Theory"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2010.01.011"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1142\/S021819670500213X"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2006.05.020"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1080\/00927870802243580"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00087-7"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603092"},{"key":"ref27","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/3242953.3242964","article-title":"A survival guide to Presburger arithmetic","volume":"5","author":"haase","year":"2018","journal-title":"SIGLOG news"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11439-2_9"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_14"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40229-1_35"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(69)90070-2"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_40"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2005.09.008"},{"key":"ref24","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","author":"greenlaw","year":"1995","journal-title":"Limits to Parallel Computation P-Completeness Theory"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.2307\/1994067"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90028-3"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90020-8"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.12.042"},{"key":"ref51","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/2893582.2893585","article-title":"The complexity of reachability in vector addition systems","volume":"1","author":"schmitz","year":"2016","journal-title":"SIGLOG news"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24537-9_15"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_39"},{"key":"ref56","author":"zetzsche","year":"2016","journal-title":"Monoids as Storage Mechanisms"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90101-2"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.3934\/era.2009.16.44"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/117"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/11532231_25"},{"key":"ref10","first-page":"128:1","article-title":"The Taming of the Semi-Linear Set","volume":"55","author":"chistikov","year":"2016","journal-title":"ICALP 95 Automata Languages and Programming"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316369"},{"key":"ref40","first-page":"368","article-title":"The rational subset membership problem for groups: a survey","volume":"422","author":"lohrey","year":"2016","journal-title":"Groups St Andrews 2013"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934552"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456932"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90003-Z"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.04.002"},{"key":"ref17","first-page":"127:1","article-title":"Solutions of Word Equations Over Partially Commutative Structures","volume":"55","author":"diekert","year":"2016","journal-title":"Automata Languages and Programming ICALP 2016"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_45"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1142\/2563"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"ref3","article-title":"Rational subsets of groups","volume":"abs 1012 1532","author":"bartholdi","year":"2010","journal-title":"CoRR"},{"key":"ref6","first-page":"14:1","article-title":"Affine Extensions of Integer Vector Addition Systems with States","volume":"118","author":"blondin","year":"2018","journal-title":"CONCUR 98 Concurrency Theory"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1145\/3105908"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1976-0396605-3"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90036-1"},{"key":"ref7","article-title":"Theory of Well-Structured Transition Systems and Extended Vector-Addition Systems","author":"bonnet","year":"2013","journal-title":"Thèse de doctorat"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_22"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70545-1_25"},{"key":"ref45","author":"papadimitriou","year":"1994","journal-title":"Computational Complexity"},{"key":"ref48","first-page":"92","article-title":"Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt","author":"presburger","year":"1929","journal-title":"Comptes Rendus du I congres de Mathematiciens des Pays Slaves"},{"key":"ref47","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/3-540-53904-2_94","article-title":"Minimal Solutions of Linear Diophantine Systems: Bounds and Algorithms","volume":"488","author":"pottier","year":"1991","journal-title":"Rewriting Techniques and Applications RTA'97"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.014"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2007.08.025"},{"key":"ref44","author":"minsky","year":"1967","journal-title":"Computation Finite and Infinite Machines"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9808-3"}],"event":{"name":"2019 34th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)","location":"Vancouver, BC, Canada","start":{"date-parts":[[2019,6,24]]},"end":{"date-parts":[[2019,6,27]]}},"container-title":["2019 34th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/8765678\/8785654\/08785850.pdf?arnumber=8785850","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,19]],"date-time":"2022-07-19T20:18:53Z","timestamp":1658261933000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/8785850\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":58,"URL":"https:\/\/doi.org\/10.1109\/lics.2019.8785850","relation":{},"subject":[],"published":{"date-parts":[[2019,6]]}}}