{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:52Z","timestamp":1750219852617,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T00:00:00Z","timestamp":1674000000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/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"}]},{"name":"Research Foundation \u2013 Flanders","award":["G030020N"],"award-info":[{"award-number":["G030020N"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>\n            We study the reachability problem for continuous one-counter automata, COCA for short. In such automata, transitions are guarded by upper- and lower-bound tests against the counter value. Additionally, the counter updates associated with taking transitions can be (non-deterministically) scaled down by a nonzero factor between zero and one. Our three main results are as follows: we prove (1)\u00a0that the reachability problem for COCA with global upper- and lower-bound tests is in NC\n            <jats:sup>2<\/jats:sup>\n            ; (2)\u00a0that, in general, the problem is decidable in polynomial time; and (3)\u00a0that it is NP-complete for COCA with parametric counter updates and bound tests.\n          <\/jats:p>","DOI":"10.1145\/3558549","type":"journal-article","created":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T11:13:42Z","timestamp":1661253222000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Continuous One-counter Automata"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2914-2734","authenticated-orcid":false,"given":"Michael","family":"Blondin","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Sherbrooke, Sherbrooke, Qu\u00e9bec, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6281-9693","authenticated-orcid":false,"given":"Tim","family":"Leys","sequence":"additional","affiliation":[{"name":"University of Antwerp, Antwerpen, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4535-6508","authenticated-orcid":false,"given":"Filip","family":"Mazowiecki","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Software Systems, Saarbr\u00fccken, Saarland, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8477-2849","authenticated-orcid":false,"given":"Philip","family":"Offtermatt","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Sherbrooke;, Sherbrooke, Qu\u00e9bec, Canada, and Max Planck Institute for Software Systems, Saarbr\u00fccken, Saarland, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1200-4952","authenticated-orcid":false,"given":"Guillermo","family":"P\u00e9rez","sequence":"additional","affiliation":[{"name":"University of Antwerp \u2013 Flanders Make, Antwerpen, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,1,18]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167242"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_2_4_2","volume-title":"Principles of Model Checking","author":"Baier Christel","year":"2008","unstructured":"Christel Baier and Joost-Pieter Katoen. 2008. Principles of Model Checking. MIT Press."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005068"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470525"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-15(3:33)2019"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-011-0111-7"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/174433"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.07.011"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017096"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316369"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.004"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04081-8_25"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33512-9_6"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56939-1_82"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28644-8_25"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785796"},{"key":"e_1_3_2_19_2","volume-title":"The Reachability Problem Requires Exponential Space","author":"Lipton Richard J.","year":"1976","unstructured":"Richard J. Lipton. 1976. The Reachability Problem Requires Exponential Space. Technical Report 62. Yale University. http:\/\/cpsc.yale.edu\/sites\/default\/files\/files\/tr63.pdf."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802477"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/1095587"},{"key":"e_1_3_2_23_2","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","year":"1994","unstructured":"Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90076-6"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558549","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558549","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:09Z","timestamp":1750178829000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558549"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,18]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3558549"],"URL":"https:\/\/doi.org\/10.1145\/3558549","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2023,1,18]]},"assertion":[{"value":"2021-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-07","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}