{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T22:00:55Z","timestamp":1742940055968,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031572302"},{"type":"electronic","value":"9783031572319"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T00:00:00Z","timestamp":1712361600000},"content-version":"vor","delay-in-days":96,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>\nA <jats:italic>k<\/jats:italic>-Counter Net (<jats:italic>k<\/jats:italic>-CN) is a finite-state automaton equipped with <jats:italic>k<\/jats:italic> integer counters that are not allowed to become negative, but do not have explicit zero tests. This language-recognition model can be thought of as labelled vector addition systems with states, some of which are accepting. Certain decision problems for <jats:italic>k<\/jats:italic>-CNs become easier, or indeed decidable, when the dimension <jats:italic>k<\/jats:italic> is small. Yet, little is known about the effect that the dimension <jats:italic>k<\/jats:italic> has on the class of languages recognised by <jats:italic>k<\/jats:italic>-CNs. Specifically, it would be useful if we could simplify algorithmic reasoning by reducing the dimension of a given CN.<\/jats:p><jats:p>To this end, we introduce the notion of dimension-primality for <jats:italic>k<\/jats:italic>-CN, whereby a <jats:italic>k<\/jats:italic>-CN is prime if it recognises a language that cannot be decomposed into a finite intersection of languages recognised by <jats:italic>d<\/jats:italic>-CNs, for some <jats:inline-formula><jats:alternatives><jats:tex-math>$$d&lt;k$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We show that primality is undecidable. We also study two related notions: dimension-minimality (where we seek a single language-equivalent <jats:italic>d<\/jats:italic>-CN of lower dimension) and language regularity. Additionally, we explore the trade-offs in expressiveness between dimension and non-determinism for CN.<\/jats:p>","DOI":"10.1007\/978-3-031-57231-9_11","type":"book-chapter","created":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T18:01:54Z","timestamp":1712340114000},"page":"229-249","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dimension-Minimality and Primality of Counter Nets"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9021-1175","authenticated-orcid":false,"given":"Shaull","family":"Almagor","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5588-8287","authenticated-orcid":false,"given":"Guy","family":"Avni","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1653-4069","authenticated-orcid":false,"given":"Henry","family":"Sinclair-Banks","sequence":"additional","affiliation":[]},{"given":"Asaf","family":"Yeshurun","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,6]]},"reference":[{"key":"11_CR1","unstructured":"Shaull Almagor, Udi Boker, Piotr Hofman, and Patrick Totzke. Parametrized universality problems for one-counter nets. In 31st International Conference on Concurrency Theory (CONCUR 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2020."},{"key":"11_CR2","unstructured":"Shaull Almagor and Asaf Yeshurun. Determinization of one-counter nets. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2022."},{"key":"11_CR3","doi-asserted-by":"publisher","unstructured":"Michel Blockelet and Sylvain Schmitz. Model checking coverability graphs of vector addition systems. In Filip Murlak and Piotr Sankowski, editors, Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings, volume 6907 of Lecture Notes in Computer Science, pages 108\u2013119. Springer, 2011.https:\/\/doi.org\/10.1007\/978-3-642-22993-0_13.","DOI":"10.1007\/978-3-642-22993-0_13"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Michael Blondin, Matthias Englert, Alain Finkel, Stefan G\u00f6ller, Christoph Haase, Ranko Lazi\u0107, Pierre McKenzie, and Patrick Totzke. The reachability problem for two-dimensional vector addition systems with states. Journal of the ACM (JACM), 68(5):1\u201343, 2021.","DOI":"10.1145\/3464794"},{"key":"11_CR5","unstructured":"Sougata Bose, David Purser, and Patrick Totzke. History-deterministic vector addition systems. arXiv preprint arXiv:2305.01981, 2023."},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Maria\u00a0Paola Cabasino, Alessandro Giua, and Carla Seatzu. Diagnosability of discrete-event systems using labeled Petri nets. IEEE Transactions on Automation Science and Engineering, 11(1):144\u2013153, 2013.","DOI":"10.1109\/TASE.2013.2289360"},{"key":"11_CR7","unstructured":"Wojciech Czerwi\u0144ski, Diego Figueira, and Piotr Hofman. Universality problem for unambiguous vass. In 31st International Conference on Concurrency Theory (CONCUR 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2020."},{"key":"11_CR8","unstructured":"Wojciech Czerwi\u0144ski, S\u0142awomir Lasota, Ranko Lazi\u0107, J\u00e9r\u00f4me Leroux, and Filip Mazowiecki. Reachability in fixed dimension vector addition systems with states. In 31st International Conference on Concurrency Theory (CONCUR 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2020."},{"key":"11_CR9","unstructured":"Wojciech Czerwi\u0144ski, Slawomir Lasota, Christof L\u00f6ding, and Radoslaw Pi\u00f3rkowski. New pumping technique for 2-dimensional VASS. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019."},{"key":"11_CR10","unstructured":"Wojciech Czerwi\u0144ski, S\u0142awomir Lasota, and \u0141ukasz Orlikowski.Improved lower bounds for reachability in vector addition systems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2021."},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Wojciech Czerwi\u0144ski and \u0141ukasz Orlikowski. Reachability in vector addition systems is Ackermann-complete. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1229\u20131240. IEEE, 2022.","DOI":"10.1109\/FOCS52979.2021.00120"},{"key":"11_CR12","doi-asserted-by":"publisher","unstructured":"St\u00e9phane Demri. On selective unboundedness of VASS. J. Comput. Syst. Sci., 79(5):689\u2013713, 2013. https:\/\/doi.org\/10.1016\/j.jcss.2013.01.014.","DOI":"10.1016\/j.jcss.2013.01.014"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Javier Esparza. Decidability and complexity of petri net problems\u2013an introduction. Lectures on Petri Nets I: Basic Models: Advances in Petri Nets, pages 374\u2013428, 2005.","DOI":"10.1007\/3-540-65306-6_20"},{"key":"11_CR14","unstructured":"Diego Figueira. Co-finiteness of VASS coverability languages. working paper or preprint, July 2019. URL: https:\/\/hal.science\/hal-02193089."},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Diego Figueira, Santiago Figueira, Sylvain Schmitz, and Philippe Schnoebelen. Ackermannian and primitive-recursive bounds with dickson\u2019s lemma. In 2011 IEEE 26th Annual Symposium on Logic in Computer Science, pages 269\u2013278. IEEE, 2011.","DOI":"10.1109\/LICS.2011.39"},{"key":"11_CR16","unstructured":"Alain Finkel, J\u00e9r\u00f4me Leroux, and Gr\u00e9goire Sutre. Reachability for two-counter machines with one test and one reset. In FSTTCS 2018-38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, volume 122, pages 31\u20131. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018."},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Sheila\u00a0A. Greibach. Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7(3):311\u2013324, 1978.","DOI":"10.1016\/0304-3975(78)90020-8"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Christoph Haase, Stephan Kreutzer, Jo\u00ebl Ouaknine, and James Worrell.Reachability in succinct and parametric one-counter automata. In CONCUR 2009-Concurrency Theory: 20th International Conference, CONCUR 2009, Bologna, Italy, September 1-4, 2009. Proceedings 20, pages 369\u2013383. Springer, 2009.","DOI":"10.1007\/978-3-642-04081-8_25"},{"key":"11_CR19","unstructured":"Michel Henri\u00a0The\u00f3dore Hack. Petri net language. Computation Structures Group Memo 124, 1976. URL: http:\/\/publications.csail.mit.edu\/lcs\/pubs\/pdf\/MIT-LCS-TR-159.pdf."},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Piotr Hofman, Richard Mayr, and Patrick Totzke. Decidability of weak simulation on one-counter nets. In 2013 28th Annual ACM\/IEEE Symposium on Logic in Computer Science, pages 203\u2013212. IEEE, 2013.","DOI":"10.1109\/LICS.2013.26"},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Piotr Hofman and Patrick Totzke. Trace inclusion for one-counter nets revisited. In Reachability Problems: 8th International Workshop, RP 2014, Oxford, UK, September 22-24, 2014. Proceedings 8, pages 151\u2013162. Springer, 2014.","DOI":"10.1007\/978-3-319-11439-2_12"},{"key":"11_CR22","unstructured":"I.\u00a0Jecker, N.\u00a0Mazzocchi, and P.\u00a0Wolf. Decomposing permutation automata. In Proc. 32nd CONCUR, volume 203 of LIPIcs, pages 18:1\u201318:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2021."},{"key":"11_CR23","unstructured":"Ismael\u00a0R Jecker, Orna Kupferman, and Nicolas Mazzocchi. Unary prime languages. In 45th International Symposium on Mathematical Foundations of Computer Science, volume 170, 2020."},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Orna Kupferman and Jonathan Mosheiff. Prime languages. Information and Computation, 240:90\u2013107, 2015.","DOI":"10.1016\/j.ic.2014.09.010"},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"J\u00e9r\u00f4me Leroux. The reachability problem for petri nets is not primitive recursive. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1241\u20131252. IEEE, 2022.","DOI":"10.1109\/FOCS52979.2021.00121"},{"key":"11_CR26","doi-asserted-by":"crossref","unstructured":"J\u00e9r\u00f4me Leroux and Gr\u00e9goire Sutre. On flatness for 2-dimensional vector addition systems with states. In CONCUR, volume\u00a04, pages 402\u2013416. Springer, 2004.","DOI":"10.1007\/978-3-540-28644-8_26"},{"key":"11_CR27","doi-asserted-by":"crossref","unstructured":"Elaine Render and Mark Kambites. Rational subsets of polycyclic monoids and valence automata. Information and Computation, 207(11):1329\u20131339, 2009.","DOI":"10.1016\/j.ic.2009.02.012"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"R\u00fcdiger Valk and Guy Vidal-Naquet. Petri nets and regular languages.Journal of Computer and system Sciences, 23(3):299\u2013325, 1981.","DOI":"10.1016\/0022-0000(81)90067-2"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-57231-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T16:04:11Z","timestamp":1714752251000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-57231-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031572302","9783031572319"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-57231-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"6 April 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 April 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2024\/conferences\/fossacs\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"79","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}