{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T20:17:22Z","timestamp":1784837842518,"version":"3.55.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T00:00:00Z","timestamp":1605484800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM SIGLOG News"],"published-print":{"date-parts":[[2020,11,16]]},"abstract":"<jats:p>Petri nets form a widespread model of concurrency well suited for the verification of systems with infinitely many configurations. Deciding configuration reachability in Petri nets, which plays a central role in their formal analysis, suffers from a nonelementary time complexity lower bound. We survey relaxations that alleviate this tremendous complexity, both for classical Petri nets and for extensions with affine transformations, branching rules and colored tokens.<\/jats:p>","DOI":"10.1145\/3436980.3436984","type":"journal-article","created":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T02:30:49Z","timestamp":1606271449000},"page":"29-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["The ABCs of petri net reachability relaxations"],"prefix":"10.1145","volume":"7","author":[{"given":"Michael","family":"Blondin","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Sherbrooke, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,11,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2774283.2774786"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.12.010"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90067-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40229-1_35"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-7(4:4)2011"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2032305.2032319"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.14"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105908"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3329995.3330003"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2018.14"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394741"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516515"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2518188"},{"key":"e_1_2_1_14_1","volume-title":"Proc. 47th International Colloquium on Automata, Languages and Programming (ICALP). To appear.","author":"Bumpus Georgina","year":"2020"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.06.017"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316369"},{"key":"e_1_2_1_17_1","volume-title":"Proc. 8th European Workshop on Application and Theory of Petri nets","volume":"340","author":"David Ren\u00e9","year":"1987"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1824006"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018438.1021843"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792734.1792766"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/646486.694620"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45190-5_22"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-11(4:15)2015"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/646252.686157"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2379396.2379398"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-016-0272-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_40"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2751290.2751292"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.04.014"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146681"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90020-8"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17127-8_15"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11439-2_9"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1786698.1786706"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/647843.736437"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2018.24"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/3329995.3330000"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90041-0"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230977.3230999"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629608"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802201"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90173-D"},{"key":"e_1_2_1_43_1","volume-title":"VASS reachability in three steps. CoRR abs\/1812.11966","author":"Lasota S\u0142awomir","year":"2018"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1497079.1497082"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2733375"},{"key":"e_1_2_1_46_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_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785796"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28644-8_26"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40184-8_12"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802477"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2017.43"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1858681.1858734"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25543-5_7"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/646232.682076"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126698000043"},{"key":"e_1_2_1_58_1","first-page":"217","article-title":"Karp-Miller Trees for a Branching Extension of VASS","volume":"7","author":"Verma Kumar Neeraj","year":"2005","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/11532231_25"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218843009002002"}],"container-title":["ACM SIGLOG News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3436980.3436984","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3436980.3436984","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:20Z","timestamp":1750197740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3436980.3436984"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,16]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,11,16]]}},"alternative-id":["10.1145\/3436980.3436984"],"URL":"https:\/\/doi.org\/10.1145\/3436980.3436984","relation":{},"ISSN":["2372-3491"],"issn-type":[{"value":"2372-3491","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,16]]},"assertion":[{"value":"2020-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}