{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T04:26:50Z","timestamp":1781756810478,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T00:00:00Z","timestamp":1720396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,7,8]]},"DOI":"10.1145\/3661814.3662116","type":"proceedings-article","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T12:30:12Z","timestamp":1718973012000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Separability Problem of VASS Reachability Languages"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-5621-6568","authenticated-orcid":false,"given":"Eren","family":"Keskin","sequence":"first","affiliation":[{"name":"Computer Science, TU Braunschweig, Braunschweig, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8495-671X","authenticated-orcid":false,"given":"Roland","family":"Meyer","sequence":"additional","affiliation":[{"name":"Computer Science, TU Braunschweig, Braunschweig, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1","volume":"254","author":"Baumann P.","year":"2023","unstructured":"P. Baumann, R. Meyer, and G. Zetzsche. Regular separability in B\u00fcchi VASS. In STACS, volume 254 of LIPIcs, pages 9:1--9:19, 2023.","journal-title":"Regular separability in B\u00fcchi VASS. In STACS"},{"key":"e_1_3_2_1_2_1","first-page":"1","volume-title":"International Congress on Logic, Method, and Philosophy of Science","author":"B\u00fcchi J. R.","year":"1962","unstructured":"J. R. B\u00fcchi. On a decision method in restricted second order arithmetic. In International Congress on Logic, Method, and Philosophy of Science, pages 1--12. Stanford University Press, 1962."},{"key":"e_1_3_2_1_3_1","series-title":"LIPIcs","first-page":"1","volume-title":"ICALP","author":"Clemente L.","year":"2017","unstructured":"L. Clemente, W Czerwi\u0144ski, S. Lasota, and C. Paperman. Regular separability of Parikh automata. In ICALP, volume 80 of LIPIcs, pages 117:1--117:13. Dagstuhl, 2017."},{"key":"e_1_3_2_1_4_1","series-title":"LIPIcs","first-page":"1","volume-title":"STACS","author":"Clemente L.","year":"2017","unstructured":"L. Clemente, W. Czerwi\u0144ski, S. Lasota, and C. Paperman. Separability of reachability sets of vector addition systems. In STACS, volume 66 of LIPIcs, pages 24:1--24:14. Dagstuhl, 2017."},{"key":"e_1_3_2_1_5_1","series-title":"LIPIcs","first-page":"1","volume-title":"ICALP","author":"Clemente L.","year":"2020","unstructured":"L. Clemente, S. Lasota, and R. Pi\u00f3rkowski. Timed games and deterministic separability. In ICALP, volume 168 of LIPIcs, pages 121:1--121:16. Dagstuhl, 2020."},{"issue":"5","key":"e_1_3_2_1_6_1","first-page":"511","volume":"5","author":"Commoner F. G.","year":"1971","unstructured":"F. G. Commoner, A. W. Holt, S. Even, and A. Pnueli. Marked directed graphs. JCSS, 5(5):511--523, 1971.","journal-title":"Marked directed graphs. JCSS"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005079"},{"key":"e_1_3_2_1_8_1","series-title":"LIPIcs","first-page":"1","volume-title":"CONCUR","author":"Czerwi\u0144ski W.","year":"2018","unstructured":"W. Czerwi\u0144ski, S. Lasota, R. Meyer, S. Muskalla, K. Narayan Kumar, and P. Saivasan. Regular separability of well-structured transition systems. In CONCUR, volume 118 of LIPIcs, pages 35:1--35:18. Dagstuhl, 2018."},{"key":"e_1_3_2_1_9_1","first-page":"1229","volume-title":"FOCS","author":"Czerwi\u0144ski W.","year":"2021","unstructured":"W. Czerwi\u0144ski and \u0141. Orlikowski. Reachability in vector addition systems is Ackermann-complete. In FOCS, pages 1229--1240. IEEE, 2021."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394776"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.014"},{"key":"e_1_3_2_1_12_1","volume-title":"Acta Informatica, 2:143--161","author":"Genrich H. J.","year":"1973","unstructured":"H. J. Genrich and K. Lautenbach. Synchronisationsgraphen. Acta Informatica, 2:143--161, 1973."},{"issue":"2","key":"e_1_3_2_1_13_1","first-page":"147","volume":"3","author":"Karp R. M.","year":"1969","unstructured":"R. M. Karp and R. E. Miller. Parallel program schemata. JCSS, 3(2):147--195, 1969.","journal-title":"Parallel program schemata. JCSS"},{"key":"e_1_3_2_1_14_1","series-title":"LIPIcs","first-page":"1","volume-title":"CONCUR","author":"Keskin E.","year":"2023","unstructured":"E. Keskin and R. Meyer. Separability and non-determinizability of WSTS. In CONCUR, volume 279 of LIPIcs, pages 8:1--8:17. Dagstuhl, 2023."},{"key":"e_1_3_2_1_15_1","volume-title":"On the separability problem of VASS reachability languages. CoRR, abs\/2401.16095","author":"Keskin Eren","year":"2024","unstructured":"Eren Keskin and Roland Meyer. On the separability problem of VASS reachability languages. CoRR, abs\/2401.16095, 2024."},{"key":"e_1_3_2_1_16_1","series-title":"LIPIcs","first-page":"1","volume-title":"FSTTCS","author":"K\u00f6cher C.","year":"2023","unstructured":"C. K\u00f6cher and G. Zetzsche. Regular separators for VASS coverability languages. In FSTTCS, volume 284 of LIPIcs, pages 15:1--15:19. Dagstuhl, 2023."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2933579"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802201"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90173-D"},{"key":"e_1_3_2_1_20_1","series-title":"LIPIcs","first-page":"1","volume-title":"STACS","author":"Lasota S.","year":"2022","unstructured":"S. Lasota. Improved Ackermannian lower bound for the Petri nets reachability problem. In STACS, volume 219 of LIPIcs, pages 46:1--46:15. Dagstuhl, 2022."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.10"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926421"},{"key":"e_1_3_2_1_23_1","first-page":"1241","volume-title":"FOCS","author":"Leroux J.","year":"2021","unstructured":"J. Leroux. The reachability problem for Petri nets is not primitive recursive. In FOCS, pages 1241--1252. IEEE, 2021."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.16"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785796"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802477"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90036-1"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803396"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858784"},{"key":"e_1_3_2_1_30_1","volume-title":"ENS-Paris-Saclay","author":"Schmitz S.","year":"2017","unstructured":"S. Schmitz. Algorithmic Complexity of Well-Quasi-Orders. Habilitation \u00e0 diriger des recherches, ENS-Paris-Saclay, 2017."}],"event":{"name":"LICS '24: 39th Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Tallinn Estonia","acronym":"LICS '24","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","IEEE Computer Society","EACSL"]},"container-title":["Proceedings of the 39th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661814.3662116","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3661814.3662116","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:44:09Z","timestamp":1750290249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661814.3662116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":30,"alternative-id":["10.1145\/3661814.3662116","10.1145\/3661814"],"URL":"https:\/\/doi.org\/10.1145\/3661814.3662116","relation":{},"subject":[],"published":{"date-parts":[[2024,7,8]]},"assertion":[{"value":"2024-07-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}