{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T06:40:03Z","timestamp":1749192003015,"version":"3.41.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T00:00:00Z","timestamp":1745366400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T00:00:00Z","timestamp":1745366400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007065","name":"Universit\u00e0 degli Studi di Salerno","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007065","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Event Dyn Syst"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The enumeration of legal transition paths leading to a target state (or set of states) is of paramount importance in the control of discrete event systems, but is hindered by the state explosion problem. A method is proposed in this paper, in the context of Petri nets, to calculate and enumerate firing count vectors for which there exists at least an admissible transition sequence leading to a given target marking. The method is shown to improve the approach based on singular complementary transition invariants proposed by Kostin and combines an integer linear programming formulation that finds the shortest minimal solution and a branching procedure that realizes a partition of the solution set. The enumeration can be restricted to minimal solutions or extended to non-minimal ones. Moreover, the approach is extended by adding a further constraint that the target transition sequences should pass by intermediate markings (in a specific order or not). Finally, source, target and via markings can be replaced by sets of markings. Some analytical examples are discussed in detail to show the effectiveness of the proposed approach.<\/jats:p>","DOI":"10.1007\/s10626-025-00412-x","type":"journal-article","created":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T07:18:20Z","timestamp":1745392700000},"page":"87-105","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimization-based computation of bounded sequences to reach target states in DESs"],"prefix":"10.1007","volume":"35","author":[{"given":"Roberto","family":"Cordone","sequence":"first","affiliation":[]},{"given":"Francesco","family":"Basile","sequence":"additional","affiliation":[]},{"given":"Luigi","family":"Piroddi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,23]]},"reference":[{"issue":"9","key":"412_CR1","doi-asserted-by":"publisher","first-page":"2047","DOI":"10.1016\/j.automatica.2012.06.039","volume":"48","author":"F Basile","year":"2012","unstructured":"Basile F, Chiacchio P, Tommasi GD (2012) On K-diagnosability of Petri nets via integer linear programming. Automatica 48(9):2047\u20132058","journal-title":"Automatica"},{"key":"412_CR2","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.automatica.2014.12.004","volume":"52","author":"F Basile","year":"2015","unstructured":"Basile F, Cordone R, Piroddi L (2015) A branch and bound approach for the design of decentralized supervisors in Petri net models. Automatica 52:322\u2013333","journal-title":"Automatica"},{"issue":"6","key":"412_CR3","doi-asserted-by":"publisher","first-page":"2800","DOI":"10.1109\/TAC.2021.3093618","volume":"67","author":"F Basile","year":"2022","unstructured":"Basile F, Cordone R, Piroddi L (2022) Supervisory control of timed discrete event systems with logical and timed specifications. IEEE Trans Autom Control 67(6):2800\u20132815","journal-title":"IEEE Trans Autom Control"},{"key":"412_CR4","doi-asserted-by":"crossref","unstructured":"Basile F, Boussif A, De\u00a0Tommasi G, Ghazel M, Sterle C (2018) Efficient diagnosability assessment via ILP optimization: a railway benchmark. In: $$23^{\\rm rd}$$ IEEE international conference on emerging technologies and factory automation. Torino, Italy, pp 441\u2013448","DOI":"10.1109\/ETFA.2018.8502532"},{"key":"412_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2022.110689","volume":"147","author":"A Chouchane","year":"2023","unstructured":"Chouchane A, Ghazel M, Boussif A (2023) K-diagnosability analysis of bounded and unbounded petri nets using linear optimization. Automatica 147:110689","journal-title":"Automatica"},{"key":"#cr-split#-412_CR6.1","doi-asserted-by":"crossref","unstructured":"Colom JM, Silva M (1991) Convex geometry and semiflows in P\/T nets. A comparative study of algorithms for computation of minimal p-semiflows. In: Rozenberg G","DOI":"10.1007\/3-540-53863-1_22"},{"key":"#cr-split#-412_CR6.2","unstructured":"(ed) Advances in Petri nets 1990, pp 79-112. Springer, Berlin, Heidelberg"},{"issue":"10","key":"412_CR7","doi-asserted-by":"publisher","first-page":"1689","DOI":"10.1109\/TSMC.2017.2726108","volume":"48","author":"X Cong","year":"2018","unstructured":"Cong X, Fanti M, Mangini A, Li Z (2018) Decentralized diagnosis by Petri nets and integer linear programming. IEEE Trans Syst Man Cybern Syst 48(10):1689\u20131700","journal-title":"IEEE Trans Syst Man Cybern Syst"},{"issue":"1","key":"412_CR8","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1109\/TSMCA.2012.2190139","volume":"43","author":"R Cordone","year":"2013","unstructured":"Cordone R, Piroddi L (2013) Parsimonious monitor control of Petri net models of FMS. IEEE Trans Syst Man Cybern Syst 43(1):215\u2013221","journal-title":"IEEE Trans Syst Man Cybern Syst"},{"issue":"11","key":"412_CR9","doi-asserted-by":"publisher","first-page":"2772","DOI":"10.1109\/TAC.2013.2266952","volume":"58","author":"R Cordone","year":"2013","unstructured":"Cordone R, Nazeem A, Piroddi L, Reveliotis S (2013) Designing optimal deadlock avoidance policies for sequential resource allocation systems through classification theory: existence results and customized algorithms. IEEE Trans Autom Control 58(11):2772\u20132787","journal-title":"IEEE Trans Autom Control"},{"key":"412_CR10","doi-asserted-by":"crossref","unstructured":"Giua A, DiCesare F, Silva M (1992) Generalized mutual exclusion constraints on nets with uncontrollable transitions. 1992 IEEE int. conf. on systems, man, and cybernetics (Chicago, Illinois), pp 974\u2013979","DOI":"10.1109\/ICSMC.1992.271666"},{"key":"412_CR11","doi-asserted-by":"crossref","unstructured":"Kostin AE (2006) A reachability algorithm for general Petri nets based on transition invariants. In: Kr\u00e1lovi\u010d R, Urzyczyn P (eds) MFCS 2006. LNCS 4162, pp 608\u2013621. Springer, Berlin, Heidelberg, Germany","DOI":"10.1007\/11821069_53"},{"key":"412_CR12","doi-asserted-by":"crossref","unstructured":"Kostin AE (2008) Using transition invariants for reachability analysis of Petri nets. In: Kordic V (ed) Petri net, theory and applications, pp 435\u2013458. I-Tech Education and Publishing, Vienna, Austria. Chap. 19","DOI":"10.5772\/5328"},{"issue":"6","key":"412_CR13","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1109\/TAC.2003.812788","volume":"48","author":"AE Kostin","year":"2003","unstructured":"Kostin AE (2003) Reachability analysis in T-invariant-less Petri nets. IEEE Trans Autom Control 48(6):1019\u20131024","journal-title":"IEEE Trans Autom Control"},{"issue":"2","key":"412_CR14","doi-asserted-by":"publisher","first-page":"1215","DOI":"10.1109\/TASE.2015.2467165","volume":"13","author":"D Lefebvre","year":"2016","unstructured":"Lefebvre D (2016) Approaching minimal time control sequences for timed Petri nets. IEEE Trans Autom Sci Eng 13(2):1215\u20131221","journal-title":"IEEE Trans Autom Sci Eng"},{"key":"412_CR15","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-642-68353-4_47","volume-title":"Application and theory of Petri nets","author":"J Mart\u00ednez","year":"1982","unstructured":"Mart\u00ednez J, Silva M (1982) A simple and fast algorithm to obtain all invariants of a generalised Petri net. In: Girault C, Reisig W (eds) Application and theory of Petri nets. Springer, Berlin, Heidelberg, pp 301\u2013310"},{"issue":"3","key":"412_CR16","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1137\/0213029","volume":"13","author":"EW Mayr","year":"1984","unstructured":"Mayr EW (1984) An algorithm for the general Petri net reachability problem. SIAM J Comput 13(3):441\u2013459","journal-title":"SIAM J Comput"},{"key":"412_CR17","doi-asserted-by":"crossref","unstructured":"Memmi G, Roucairol G (1980) Linear algebra in net theory. In: Proceedings of the advanced course on general net theory of processes and systems: net theory and applications, pp 213\u2013223. Springer, London, UK, UK","DOI":"10.1007\/3-540-10001-6_24"},{"issue":"4","key":"412_CR18","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1109\/5.24143","volume":"77","author":"T Murata","year":"1989","unstructured":"Murata T (1989) Petri nets: properties, analysis and applications. Proc IEEE 77(4):541\u2013580","journal-title":"Proc IEEE"},{"issue":"8","key":"412_CR19","doi-asserted-by":"publisher","first-page":"4968","DOI":"10.1109\/TSMC.2023.3241101","volume":"53","author":"L Qi","year":"2023","unstructured":"Qi L, Su Y, Zhou M, Abusorrah A (2023) A state-equation-based backward approach to a legal firing sequence existence problem in petri nets. IEEE Trans Syst Man Cybern Syst 53(8):4968\u20134979","journal-title":"IEEE Trans Syst Man Cybern Syst"},{"key":"412_CR20","doi-asserted-by":"crossref","unstructured":"Reveliotis S (2005) A linear characterization of the Petri net reachability space corresponding to bounded-length fireable transition sequences and its implications for the structural analysis of process-resource nets with acyclic, quasi-live and strongly reversible process subnets. In: 44th IEEE conference on decision and control and European control conference, Seville, Spain, pp 2113\u20132118","DOI":"10.1109\/CDC.2005.1582473"},{"key":"412_CR21","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/3-540-48745-X_4","volume-title":"Application and theory of Petri nets 1999","author":"K Schmidt","year":"1999","unstructured":"Schmidt K (1999) Stubborn sets for standard properties. In: Donatelli S, Kleijn J (eds) Application and theory of Petri nets 1999. Springer, Berlin, Heidelberg, pp 46\u201365"},{"key":"412_CR22","doi-asserted-by":"crossref","unstructured":"Silva M, Teruel E, Colom JM (1998) In: Reisig W, Rozenberg G (eds) Linear algebraic and linear programming techniques for the analysis of place\/transition net systems, pp 309\u2013373. Springer, Berlin, Heidelberg","DOI":"10.1007\/3-540-65306-6_19"},{"issue":"6","key":"412_CR23","doi-asserted-by":"publisher","first-page":"3190","DOI":"10.1109\/LRA.2023.3246384","volume":"8","author":"Y Su","year":"2023","unstructured":"Su Y, Qi L, Zhou M (2023) A backward algorithm to determine the existence of legal firing sequences in ordinary petri nets. IEEE Robot Autom Lett 8(6):3190\u20133197","journal-title":"IEEE Robot Autom Lett"},{"key":"412_CR24","doi-asserted-by":"crossref","unstructured":"Watanabe T, Mizobata Y, Onaga K (1989) Legal firing sequence and related problems of petri nets. In: Proceedings of the third international workshop on Petri nets and performance models, PNPM89, pp 277\u2013286","DOI":"10.1109\/PNPM.1989.68561"}],"container-title":["Discrete Event Dynamic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-025-00412-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10626-025-00412-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-025-00412-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T06:21:42Z","timestamp":1749190902000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10626-025-00412-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,23]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["412"],"URL":"https:\/\/doi.org\/10.1007\/s10626-025-00412-x","relation":{},"ISSN":["0924-6703","1573-7594"],"issn-type":[{"type":"print","value":"0924-6703"},{"type":"electronic","value":"1573-7594"}],"subject":[],"published":{"date-parts":[[2025,4,23]]},"assertion":[{"value":"12 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}]}}