{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:31:50Z","timestamp":1758274310232,"version":"3.37.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030308056"},{"type":"electronic","value":"9783030308063"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-30806-3_15","type":"book-chapter","created":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T09:08:36Z","timestamp":1567760916000},"page":"193-201","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Coverability Is Undecidable in One-Dimensional Pushdown Vector Addition Systems with Resets"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4101-4308","authenticated-orcid":false,"given":"Sylvain","family":"Schmitz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6421-4388","authenticated-orcid":false,"given":"Georg","family":"Zetzsche","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,6]]},"reference":[{"issue":"4","key":"15_CR1","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/BF02576519","volume":"15","author":"A Arnold","year":"1978","unstructured":"Arnold, A., Latteux, M.: R\u00e9cursivit\u00e9 et c\u00f4nes rationnels ferm\u00e9s par intersection. CALCOLO 15(4), 381\u2013394 (1978). \n                    https:\/\/doi.org\/10.1007\/BF02576519","journal-title":"CALCOLO"},{"doi-asserted-by":"publisher","unstructured":"Atig, M.F., Ganty, P.: Approximating Petri net reachability along context-free traces. In: FSTTCS 2011. Leibniz International Proceedings in Informatics, vol. 13, pp. 152\u2013163 (2011). \n                    https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2011.152","key":"15_CR2","DOI":"10.4230\/LIPIcs.FSTTCS.2011.152"},{"doi-asserted-by":"publisher","unstructured":"Blondin, M., Finkel, A., G\u00f6ller, S., Haase, C., McKenzie, P.: Reachability in two-dimensional vector addition systems with states is PSPACE-complete. In: LICS 2015, pp. 32\u201343. IEEE (2015). \n                    https:\/\/doi.org\/10.1109\/LICS.2015.14","key":"15_CR3","DOI":"10.1109\/LICS.2015.14"},{"key":"15_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BFb0055044","volume-title":"Automata, Languages and Programming","author":"C Dufourd","year":"1998","unstructured":"Dufourd, C., Finkel, A., Schnoebelen, P.: Reset nets between decidability and undecidability. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 103\u2013115. Springer, Heidelberg (1998). \n                    https:\/\/doi.org\/10.1007\/BFb0055044"},{"doi-asserted-by":"publisher","unstructured":"Englert, M., Lazi\u0107, R., Totzke, P.: Reachability in two-dimensional unary vector addition systems with states is NL-complete. In: LICS 2016, pp. 477\u2013484. ACM (2016). \n                    https:\/\/doi.org\/10.1145\/2933575.2933577","key":"15_CR5","DOI":"10.1145\/2933575.2933577"},{"key":"15_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/3-540-46541-3_29","volume-title":"STACS 2000","author":"A Finkel","year":"2000","unstructured":"Finkel, A., Sutre, G.: Decidability of reachability problems for classes of two counters automata. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 346\u2013357. Springer, Heidelberg (2000). \n                    https:\/\/doi.org\/10.1007\/3-540-46541-3_29"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0304-3975(79)90041-0","volume":"8","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Pansiot, J.J.: On the reachability problem for 5-dimensional vector addition systems. Theor. Comput. Sci. 8, 135\u2013159 (1979). \n                    https:\/\/doi.org\/10.1016\/0304-3975(79)90041-0","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"15_CR8","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0022-0000(69)80011-5","volume":"3","author":"RM Karp","year":"1969","unstructured":"Karp, R.M., Miller, R.E.: Parallel program schemata. J. Comput. Syst. Sci. 3(2), 147\u2013195 (1969). \n                    https:\/\/doi.org\/10.1016\/S0022-0000(69)80011-5","journal-title":"J. Comput. Syst. Sci."},{"unstructured":"Lazi\u0107, R.: The reachability problem for vector addition systems with a stack is not elementary. \n                    arXiv:1310.1767\n                    \n                   [cs.LO] (2013). Presented orally at RP 2012","key":"15_CR9"},{"unstructured":"Leroux, J., Praveen, M., Schnoebelen, Ph., Sutre, G.: On functions weakly computable by pushdown Petri nets and related systems (2019). \n                    arXiv:1904.04090\n                    \n                   [cs.FL]. extended abstract published in: RP 2014. Lect. Notes in Comput. Sci., vol. 8762, pp. 190\u2013202. Springer (2014)","key":"15_CR10"},{"doi-asserted-by":"publisher","unstructured":"Leroux, J., Praveen, M., Sutre, G.: Hyper-Ackermannian bounds for pushdown vector addition systems. In: CSL-LICS 2014. IEEE (2014). \n                    https:\/\/doi.org\/10.1145\/2603088.2603146","key":"15_CR11","DOI":"10.1145\/2603088.2603146"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-662-47666-6_26","volume-title":"Automata, Languages, and Programming","author":"J Leroux","year":"2015","unstructured":"Leroux, J., Sutre, G., Totzke, P.: On the coverability problem for pushdown vector addition systems in one dimension. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 324\u2013336. Springer, Heidelberg (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-662-47666-6_26"},{"issue":"3","key":"15_CR13","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1145\/322261.322271","volume":"28","author":"EW Mayr","year":"1981","unstructured":"Mayr, E.W., Meyer, A.R.: The complexity of the finite containment problem for Petri nets. J. ACM 28(3), 561\u2013576 (1981). \n                    https:\/\/doi.org\/10.1145\/322261.322271","journal-title":"J. ACM"},{"issue":"3","key":"15_CR14","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"ML Minsky","year":"1961","unstructured":"Minsky, M.L.: Recursive unsolvability of Post\u2019s problem of \u201ctag\u201d and other topics in theory of Turing machines. Ann. Math. 74(3), 437\u2013455 (1961). \n                    https:\/\/doi.org\/10.2307\/1970290","journal-title":"Ann. Math."},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.entcs.2008.12.042","volume":"223","author":"Klaus Reinhardt","year":"2008","unstructured":"Reinhardt, K.: Reachability in Petri nets with inhibitor arcs. In: RP 2008. Electronic Notes in Theoretical Computer Science, vol. 223, pp. 239\u2013264 (2008). \n                    https:\/\/doi.org\/10.1016\/j.entcs.2008.12.042\n                    \n                  . Based on a manuscript already available from the author\u2019s webpage in 1995","journal-title":"Electronic Notes in Theoretical Computer Science"},{"unstructured":"Zetzsche, G.: The emptiness problem for valence automata over graph monoids. Inform. Comput. (2018)   arXiv:1710.07528    [cs.FL]. To appear","key":"#cr-split#-15_CR16.1"},{"unstructured":"extended abstract published in: RP 2015. Lect. Notes in Comput. Sci., vol. 9328, pp. 166-178. Springer (2015)","key":"#cr-split#-15_CR16.2"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-30806-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T09:09:06Z","timestamp":1567760946000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-30806-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030308056","9783030308063"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-30806-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"6 September 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Reachability Problems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Brussels","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Belgium","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rp2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.uclouvain.be\/rp2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}