{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T16:10:17Z","timestamp":1762013417833,"version":"build-2065373602"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,7,8]],"date-time":"2019-07-08T00:00:00Z","timestamp":1562544000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,8]],"date-time":"2019-07-08T00:00:00Z","timestamp":1562544000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["18-11193S"],"award-info":[{"award-number":["18-11193S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/L016400\/1"],"award-info":[{"award-number":["EP\/L016400\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s00236-019-00338-6","type":"journal-article","created":{"date-parts":[[2019,7,8]],"date-time":"2019-07-08T14:02:46Z","timestamp":1562594566000},"page":"537-552","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Structural liveness of Petri nets is ExpSpace-hard and decidable"],"prefix":"10.1007","volume":"56","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8738-9850","authenticated-orcid":false,"given":"Petr","family":"Jan\u010dar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Purser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,8]]},"reference":[{"issue":"1\u20132","key":"338_CR1","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1006\/inco.1999.2843","volume":"160","author":"PA Abdulla","year":"2000","unstructured":"Abdulla, P.A., Cerans, K., Jonsson, B., Tsay, Y.: Algorithmic analysis of programs with well quasi-ordered domains. Inf. Comput. 160(1\u20132), 109\u2013127 (2000). \n                    https:\/\/doi.org\/10.1006\/inco.1999.2843","journal-title":"Inf. Comput."},{"key":"338_CR2","doi-asserted-by":"publisher","unstructured":"Barkaoui, K., Pradat-Peyre, J.: On liveness and controlled siphons in Petri nets. In: Billington, J., Reisig, W. (eds.) Application and Theory of Petri Nets 1996, 17th International Conference, Osaka, Japan, June 24\u201328, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1091, pp. 57\u201372. Springer, Berlin (1996). \n                    https:\/\/doi.org\/10.1007\/3-540-61363-3_4","DOI":"10.1007\/3-540-61363-3_4"},{"issue":"6","key":"338_CR3","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.ipl.2016.01.011","volume":"116","author":"E Best","year":"2016","unstructured":"Best, E., Esparza, J.: Existence of home states in Petri nets is decidable. Inf. Process. Lett. 116(6), 423\u2013427 (2016). \n                    https:\/\/doi.org\/10.1016\/j.ipl.2016.01.011","journal-title":"Inf. Process. Lett."},{"key":"338_CR4","doi-asserted-by":"publisher","unstructured":"Cardoza, E., Lipton, R.J., Meyer, A.R.: Exponential space complete problems for petri nets and commutative semigroups: preliminary report. In: Proceedings of the 8th Annual ACM Symposium on Theory of Computing, May 3\u20135, 1976, Hershey, Pennsylvania, USA, pp. 50\u201354 (1976). \n                    https:\/\/doi.org\/10.1145\/800113.803630","DOI":"10.1145\/800113.803630"},{"issue":"5","key":"338_CR5","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/S0022-0000(71)80013-2","volume":"5","author":"F Commoner","year":"1971","unstructured":"Commoner, F., Holt, A.W., Even, S., Pnueli, A.: Marked directed graphs. J. Comput. Syst. Sci. 5(5), 511\u2013523 (1971)","journal-title":"J. Comput. Syst. Sci."},{"key":"338_CR6","doi-asserted-by":"publisher","unstructured":"Czerwi\u0144ski, W., Lasota, S., Lazi\u0107, R., Leroux, J., Mazowiecki, F.: The reachability problem for Petri nets is not elementary. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 24\u201333. ACM, New York (2019). \n                    https:\/\/doi.org\/10.1145\/3313276.3316369","DOI":"10.1145\/3313276.3316369"},{"key":"338_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511526558","volume-title":"Free Choice Petri Nets","author":"J Desel","year":"1995","unstructured":"Desel, J., Esparza, J.: Free Choice Petri Nets. Cambridge University Press, New York (1995)"},{"key":"338_CR8","doi-asserted-by":"publisher","unstructured":"Esparza, J.: Decidability and complexity of Petri net problems\u2014an introduction. In: Reisig, W., Rozenberg, G. (eds.) Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, LNCS, vol. 1491, pp. 374\u2013428. Springer, Berlin (1996). \n                    https:\/\/doi.org\/10.1007\/3-540-65306-6_20","DOI":"10.1007\/3-540-65306-6_20"},{"issue":"3","key":"338_CR9","doi-asserted-by":"publisher","first-page":"28","DOI":"10.2168\/LMCS-8(3:28)2012","volume":"8","author":"A Finkel","year":"2012","unstructured":"Finkel, A., Goubault-Larrecq, J.: Forward analysis for WSTS, part II: complete WSTS. Log. Methods Comput. Sci. 8(3), 28 (2012). \n                    https:\/\/doi.org\/10.2168\/LMCS-8(3:28)2012","journal-title":"Log. Methods Comput. Sci."},{"issue":"1\u20132","key":"338_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0304-3975(00)00102-X","volume":"256","author":"A Finkel","year":"2001","unstructured":"Finkel, A., Schnoebelen, P.: Well-structured transition systems everywhere!. Theor. Comput. Sci. 256(1\u20132), 63\u201392 (2001). \n                    https:\/\/doi.org\/10.1016\/S0304-3975(00)00102-X","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"338_CR11","doi-asserted-by":"publisher","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg, S., Spanier, E.H.: Semigroups, Presburger formulas, and languages. Pac. J. Math. 16(2), 285\u2013296 (1966)","journal-title":"Pac. J. Math."},{"key":"338_CR12","volume-title":"Petri Nets and Commutative Semigroups","author":"M Hack","year":"1974","unstructured":"Hack, M.: Petri Nets and Commutative Semigroups. Massachusetts Institute of Technology, Project MAC. Cambridge, MA, USA (1974)"},{"key":"338_CR13","doi-asserted-by":"publisher","unstructured":"Hack, M.: The recursive equivalence of the reachability problem and the liveness problem for Petri nets and vector addition systems. In: 15th Annual Symposium on Switching and Automata Theory, New Orleans, Louisiana, USA, October 14\u201316, 1974, pp. 156\u2013164. IEEE Computer Society (1974). \n                    https:\/\/doi.org\/10.1109\/SWAT.1974.28","DOI":"10.1109\/SWAT.1974.28"},{"key":"338_CR14","unstructured":"Hack, M.: Decidability Questions for Petri Nets. Outstanding Dissertations in the Computer Sciences. Garland Publishing, New York (1975)"},{"key":"338_CR15","doi-asserted-by":"publisher","unstructured":"Jan\u010dar, P.: Deciding structural liveness of Petri nets. In: Steffen, B., Baier, C., van den Brand, M., Eder, J., Hinchey, M., Margaria, T. (eds.) SOFSEM 2017: Theory and Practice of Computer Science\u201443rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16\u201320, 2017, Proceedings, Lecture Notes in Computer Science, vol. 10139, pp. 91\u2013102. Springer, Berlin (2017). \n                    https:\/\/doi.org\/10.1007\/978-3-319-51963-0_8","DOI":"10.1007\/978-3-319-51963-0_8"},{"issue":"8","key":"338_CR16","first-page":"552","volume":"89","author":"R Johnsonbaugh","year":"1982","unstructured":"Johnsonbaugh, R., Murata, T.: Petri nets and marked graphs-mathematical models of concurrent computation. Am. Math. Mon. 89(8), 552\u2013566 (1982)","journal-title":"Am. Math. Mon."},{"key":"338_CR17","unstructured":"Leroux, J.: Vector addition systems reachability problem (a simpler solution). In: Voronkov, A. (ed.) Turing-100\u2014The Alan Turing Centenary, Manchester, UK, June 22\u201325, 2012, EasyChair, EPiC Series in Computing, vol. 10, pp. 214\u2013228 (2012). \n                    http:\/\/www.easychair.org\/publications\/?page=1673703727"},{"key":"338_CR18","doi-asserted-by":"publisher","unstructured":"Leroux, J.: Presburger vector addition systems. In: 28th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25\u201328, 2013, pp. 23\u201332. IEEE Computer Society (2013). \n                    https:\/\/doi.org\/10.1109\/LICS.2013.7","DOI":"10.1109\/LICS.2013.7"},{"key":"338_CR19","unstructured":"Leroux, J., Schmitz, S.: Reachability in vector addition systems is primitive-recursive in fixed dimension. In: 34th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, Canada, June 24\u201327, 2019. IEEE Computer Society (2019)"},{"issue":"3","key":"338_CR20","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1137\/0213029","volume":"13","author":"EW Mayr","year":"1984","unstructured":"Mayr, E.W.: An algorithm for the general Petri net reachability problem. SIAM J. Comput. 13(3), 441\u2013460 (1984). \n                    https:\/\/doi.org\/10.1137\/0213029","journal-title":"SIAM J. Comput."},{"issue":"3","key":"338_CR21","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1006\/jcom.1997.0447","volume":"13","author":"EW Mayr","year":"1997","unstructured":"Mayr, E.W.: Some complexity results for polynomial ideals. J. Complex. 13(3), 303\u2013325 (1997). \n                    https:\/\/doi.org\/10.1006\/jcom.1997.0447","journal-title":"J. Complex."},{"issue":"3","key":"338_CR22","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"EW Mayr","year":"1982","unstructured":"Mayr, E.W., Meyer, A.R.: The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. Math. 46(3), 305\u2013329 (1982)","journal-title":"Adv. Math."},{"key":"338_CR23","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0304-3975(78)90036-1","volume":"6","author":"C Rackoff","year":"1978","unstructured":"Rackoff, C.: The covering and boundedness problems for vector addition systems. Theor. Comput. Sci. 6, 223\u2013231 (1978). \n                    https:\/\/doi.org\/10.1016\/0304-3975(78)90036-1","journal-title":"Theor. Comput. Sci."},{"key":"338_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33278-4","volume-title":"Understanding Petri Nets (Modeling Techniques, Analysis Methods, Case Studies)","author":"W Reisig","year":"2013","unstructured":"Reisig, W.: Understanding Petri Nets (Modeling Techniques, Analysis Methods, Case Studies). Springer, Berlin (2013). \n                    https:\/\/doi.org\/10.1007\/978-3-642-33278-4"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-019-00338-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-019-00338-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-019-00338-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T23:16:23Z","timestamp":1594077383000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-019-00338-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,8]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["338"],"URL":"https:\/\/doi.org\/10.1007\/s00236-019-00338-6","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2019,7,8]]},"assertion":[{"value":"16 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}