{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,1]],"date-time":"2026-11-01T02:57:37Z","timestamp":1793501857046,"version":"4.5.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Leroux has proved that unreachability in Petri nets can be witnessed by a\nPresburger separator, i.e. if a marking $\\vec{m}_\\text{src}$ cannot reach a\nmarking $\\vec{m}_\\text{tgt}$, then there is a formula $\\varphi$ of Presburger\narithmetic such that: $\\varphi(\\vec{m}_\\text{src})$ holds; $\\varphi$ is forward\ninvariant, i.e., $\\varphi(\\vec{m})$ and $\\vec{m} \\rightarrow \\vec{m}'$ imply\n$\\varphi(\\vec{m}'$); and $\\neg \\varphi(\\vec{m}_\\text{tgt})$ holds. While these\nseparators could be used as explanations and as formal certificates of\nunreachability, this has not yet been the case due to their worst-case size,\nwhich is at least Ackermannian, and the complexity of checking that a formula\nis a separator, which is at least exponential (in the formula size).\n  We show that, in continuous Petri nets, these two problems can be overcome.\nWe introduce locally closed separators, and prove that: (a) unreachability can\nbe witnessed by a locally closed separator computable in polynomial time; (b)\nchecking whether a formula is a locally closed separator is in NC (so, simpler\nthan unreachability, which is P-complete).\n  We further consider the more general problem of (existential) set-to-set\nreachability, where two sets of markings are given as convex polytopes. We show\nthat, while our approach does not extend directly, we can efficiently certify\nunreachability via an altered Petri net.<\/jats:p>","DOI":"10.46298\/lmcs-20(1:15)2024","type":"journal-article","created":{"date-parts":[[2024,2,28]],"date-time":"2024-02-28T11:45:06Z","timestamp":1709120706000},"source":"Crossref","is-referenced-by-count":1,"title":["Separators in Continuous Petri Nets"],"prefix":"10.46298","volume":"Volume 20, Issue 1","author":[{"given":"Michael","family":"Blondin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Javier","family":"Esparza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2024,2,21]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/13141\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/13141\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,28]],"date-time":"2024-02-28T11:45:07Z","timestamp":1709120707000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/10017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,21]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(1:15)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2209.02767v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2209.02767v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2209.02767","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2209.02767","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,21]]},"article-number":"10017"}}