{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T15:47:23Z","timestamp":1784216843346,"version":"3.55.0"},"reference-count":50,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100003392","name":"Natural Science Foundation of Fujian Province","doi-asserted-by":"publisher","award":["2025J01054"],"award-info":[{"award-number":["2025J01054"]}],"id":[{"id":"10.13039\/501100003392","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100016808","name":"Natural Science Foundation of Xiamen Municipality","doi-asserted-by":"publisher","award":["3502Z202573035"],"award-info":[{"award-number":["3502Z202573035"]}],"id":[{"id":"10.13039\/100016808","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013804","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100013804","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["RVO 67985840"],"award-info":[{"award-number":["RVO 67985840"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["20720250160"],"award-info":[{"award-number":["20720250160"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Automatica"],"published-print":{"date-parts":[[2026,7]]},"DOI":"10.1016\/j.automatica.2026.113011","type":"journal-article","created":{"date-parts":[[2026,4,19]],"date-time":"2026-04-19T19:13:55Z","timestamp":1776626035000},"page":"113011","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":2,"special_numbering":"C","title":["Diagnosability verification for automata and Petri nets: Can we do better?"],"prefix":"10.1016","volume":"189","author":[{"given":"Shaowen","family":"Miao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr","family":"Jan\u010dar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Komenda","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom\u00e1\u0161","family":"Masopust","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aiwen","family":"Lai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"issue":"4","key":"10.1016\/j.automatica.2026.113011_b1","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1142\/S0129054111008428","article-title":"On Yen\u2019s path logic for Petri nets","volume":"22","author":"Atig","year":"2011","journal-title":"International Journal of Foundations of Computer Science"},{"key":"10.1016\/j.automatica.2026.113011_b2","unstructured":"Balun,\u00a0J., Masopust,\u00a0T., & Osi\u010dka,\u00a0P. (2023). Speed Me up If You Can: Conditional Lower Bounds on Opacity Verification. In International symposium on mathematical foundations of computer science (pp. 16:1\u201316:15)."},{"issue":"4","key":"10.1016\/j.automatica.2026.113011_b3","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1561\/2600000024","article-title":"Analysis and control for resilience of discrete event systems: Fault diagnosis, opacity and cyber security","volume":"8","author":"Basilio","year":"2021","journal-title":"Foundations and Trends\u00ae in Systems and Control"},{"issue":"2","key":"10.1016\/j.automatica.2026.113011_b4","doi-asserted-by":"crossref","first-page":"4570","DOI":"10.1016\/j.ifacol.2023.10.957","article-title":"Modular diagnosability of discrete event systems synchronized by observable or unobservable events","volume":"56","author":"Basilio","year":"2023","journal-title":"IFAC-PapersOnLine"},{"issue":"4","key":"10.1016\/j.automatica.2026.113011_b5","doi-asserted-by":"crossref","first-page":"317","DOI":"10.3233\/FI-2018-1706","article-title":"The complexity of diagnosability and opacity verification for Petri nets","volume":"161","author":"B\u00e9rard","year":"2018","journal-title":"Fundamenta Informaticae"},{"key":"10.1016\/j.automatica.2026.113011_b6","first-page":"417","article-title":"Foundation of diagnosis and predictability in probabilistic systems","volume":"Vol. 29","author":"Bertrand","year":"2014"},{"issue":"12","key":"10.1016\/j.automatica.2026.113011_b7","doi-asserted-by":"crossref","first-page":"3104","DOI":"10.1109\/TAC.2012.2200372","article-title":"A new approach for diagnosability analysis of Petri nets using verifier nets","volume":"57","author":"Cabasino","year":"2012","journal-title":"IEEE Transactions on Automatic Control"},{"issue":"1","key":"10.1016\/j.automatica.2026.113011_b8","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1109\/TCNS.2021.3124159","article-title":"Weak diagnosability of discrete-event systems","volume":"9","author":"Cao","year":"2021","journal-title":"IEEE Transactions on Control of Network Systems"},{"key":"10.1016\/j.automatica.2026.113011_b9","series-title":"Introduction to discrete event systems","author":"Cassandras","year":"2021"},{"issue":"1","key":"10.1016\/j.automatica.2026.113011_b10","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1109\/TASE.2016.2551746","article-title":"Revised test for stochastic diagnosability of discrete-event systems","volume":"15","author":"Chen","year":"2016","journal-title":"IEEE Transactions on Automation Science and Engineering"},{"key":"10.1016\/j.automatica.2026.113011_b11","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/s10626-006-6177-5","article-title":"Diagnosability of discrete event systems with modular structure","volume":"16","author":"Contant","year":"2006","journal-title":"Discrete Event Dynamic Systems: Theory and Applications"},{"key":"10.1016\/j.automatica.2026.113011_b12","series-title":"Introduction to algorithms","author":"Cormen","year":"2022"},{"key":"10.1016\/j.automatica.2026.113011_b13","doi-asserted-by":"crossref","unstructured":"Czerwinski,\u00a0W., & Orlikowski,\u00a0L. (2021). Reachability in Vector Addition Systems is Ackermann-complete. In IEEE symposium on foundations of computer science (pp. 1229\u20131240).","DOI":"10.1109\/FOCS52979.2021.00120"},{"key":"10.1016\/j.automatica.2026.113011_b14","doi-asserted-by":"crossref","unstructured":"Debouk,\u00a0R., Malik,\u00a0R., & Brandin,\u00a0B. A. (2002). A modular architecture for diagnosis of discrete event systems. In IEEE conference on decision and control (pp. 417\u2013422).","DOI":"10.1109\/CDC.2002.1184530"},{"issue":"1","key":"10.1016\/j.automatica.2026.113011_b15","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s10626-005-5238-5","article-title":"Distributed monitoring of concurrent and asynchronous systems","volume":"15","author":"Fabre","year":"2005","journal-title":"Discrete Event Dynamic Systems: Theory and Applications"},{"issue":"1","key":"10.1016\/j.automatica.2026.113011_b16","doi-asserted-by":"crossref","first-page":"24","DOI":"10.3390\/a10010024","article-title":"Problems on finite automata and the exponential time hypothesis","volume":"10","author":"Fernau","year":"2017","journal-title":"Algorithms"},{"key":"10.1016\/j.automatica.2026.113011_b17","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s10626-005-2866-8","article-title":"Modular fault diagnosis based on discrete event systems","volume":"15","author":"Garc\u00eda","year":"2005","journal-title":"Discrete Event Dynamic Systems: Theory and Applications"},{"issue":"4","key":"10.1016\/j.automatica.2026.113011_b18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2832910","article-title":"Diagnosability under weak fairness","volume":"14","author":"Germanos","year":"2015","journal-title":"ACM Transactions on Embedded Computing Systems"},{"issue":"2","key":"10.1016\/j.automatica.2026.113011_b19","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/120868177","article-title":"3-SAT faster and simpler \u2013 unique-SAT bounds for PPSZ hold in general","volume":"43","author":"Hertli","year":"2014","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"10.1016\/j.automatica.2026.113011_b20","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","article-title":"On the complexity of k-SAT","volume":"62","author":"Impagliazzo","year":"2001","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"10.1016\/j.automatica.2026.113011_b21","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0304-3975(95)00037-W","article-title":"Undecidability of bisimilarity for Petri nets and some related problems","volume":"148","author":"Jan\u010dar","year":"1995","journal-title":"Theoretical Computer Science"},{"issue":"8","key":"10.1016\/j.automatica.2026.113011_b22","doi-asserted-by":"crossref","first-page":"1318","DOI":"10.1109\/9.940942","article-title":"A polynomial algorithm for testing diagnosability of discrete-event systems","volume":"46","author":"Jiang","year":"2001","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/j.automatica.2026.113011_b23","doi-asserted-by":"crossref","unstructured":"Kozen,\u00a0D. (1977). Lower Bounds for Natural Proof Systems. In IEEE annual symposium on foundations of computer science (pp. 254\u2013266).","DOI":"10.1109\/SFCS.1977.16"},{"key":"10.1016\/j.automatica.2026.113011_b24","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/j.ins.2022.01.061","article-title":"Diagnosability of fault patterns with labeled stochastic Petri nets","volume":"593","author":"Lefebvre","year":"2022","journal-title":"Information Sciences"},{"key":"10.1016\/j.automatica.2026.113011_b25","doi-asserted-by":"crossref","DOI":"10.1016\/j.automatica.2023.111045","article-title":"Diagnosis of timed patterns for discrete event systems by means of state isolation","volume":"153","author":"Lefebvre","year":"2023","journal-title":"Automatica"},{"key":"10.1016\/j.automatica.2026.113011_b26","doi-asserted-by":"crossref","unstructured":"Leroux,\u00a0J. (2021). The Reachability Problem for Petri Nets is Not Primitive Recursive. In IEEE symposium on foundations of computer science (pp. 1241\u20131252).","DOI":"10.1109\/FOCS52979.2021.00121"},{"issue":"1","key":"10.1016\/j.automatica.2026.113011_b27","doi-asserted-by":"crossref","first-page":"13618","DOI":"10.1016\/j.ifacol.2017.08.2387","article-title":"Polynomial time verification of modular diagnosability of discrete event systems","volume":"50","author":"Li","year":"2017","journal-title":"IFAC-PapersOnLine"},{"issue":"3","key":"10.1016\/j.automatica.2026.113011_b28","doi-asserted-by":"crossref","first-page":"2044","DOI":"10.1109\/TAC.2023.3319154","article-title":"Verification of pattern\u2013pattern diagnosability in partially observed discrete event systems","volume":"69","author":"Ma","year":"2023","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/j.automatica.2026.113011_b29","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1016\/j.automatica.2018.12.019","article-title":"Complexity of detectability, opacity and A-diagnosability for modular discrete event systems","volume":"101","author":"Masopust","year":"2019","journal-title":"Automatica"},{"key":"10.1016\/j.automatica.2026.113011_b30","doi-asserted-by":"crossref","first-page":"11239","DOI":"10.1109\/TASE.2025.3531787","article-title":"Active diagnosis of time-interval automata: Time perspectives","volume":"22","author":"Miao","year":"2025","journal-title":"IEEE Transactions on Automation Science and Engineering"},{"key":"10.1016\/j.automatica.2026.113011_b31","doi-asserted-by":"crossref","first-page":"3392","DOI":"10.1109\/LCSYS.2025.3538737","article-title":"Decentralized fault diagnosis for constant-time automata","volume":"8","author":"Miao","year":"2025","journal-title":"IEEE Control Systems Letters"},{"key":"10.1016\/j.automatica.2026.113011_b32","series-title":"Computation: finite and infinite machines","author":"Minsky","year":"1967"},{"issue":"7","key":"10.1016\/j.automatica.2026.113011_b33","doi-asserted-by":"crossref","first-page":"1679","DOI":"10.1109\/TAC.2011.2124950","article-title":"Polynomial time verification of decentralized diagnosability of discrete event systems","volume":"56","author":"Moreira","year":"2011","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/j.automatica.2026.113011_b34","doi-asserted-by":"crossref","unstructured":"Oliveira,\u00a0M. d., & Wehar,\u00a0M. (2020). On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection. In International conference developments in language theory (pp. 69\u201382).","DOI":"10.1007\/978-3-030-48516-0_6"},{"issue":"3","key":"10.1016\/j.automatica.2026.113011_b35","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/1066100.1066101","article-title":"An improved exponential-time algorithm for k-SAT","volume":"52","author":"Paturi","year":"2005","journal-title":"Journal of the ACM"},{"key":"10.1016\/j.automatica.2026.113011_b36","unstructured":"Pencol\u00e9,\u00a0Y. (2004). Diagnosability Analysis of Distributed Discrete Event Systems. In Eureopean conference on artificial intelligence (pp. 43\u201347)."},{"key":"10.1016\/j.automatica.2026.113011_b37","series-title":"Petri net theory and the modeling of systems","author":"Peterson","year":"1981"},{"issue":"1","key":"10.1016\/j.automatica.2026.113011_b38","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/TASE.2006.872120","article-title":"Online fault diagnosis of discrete event systems. a Petri net-based approach","volume":"4","author":"Ram\u00edrez-Trevi\u00f1o","year":"2007","journal-title":"IEEE Transactions on Automation Science and Engineering"},{"issue":"2","key":"10.1016\/j.automatica.2026.113011_b39","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1109\/JAS.2017.7510406","article-title":"An improved approach to test diagnosability of bounded Petri nets","volume":"4","author":"Ran","year":"2017","journal-title":"IEEE\/CAA Journal of Automatica Sinica"},{"key":"10.1016\/j.automatica.2026.113011_b40","doi-asserted-by":"crossref","unstructured":"Ricker,\u00a0S. L., & Fabre,\u00a0E. (2000). On the construction of modular observers and diagnosers for discrete-event systems. In IEEE conference on decision and control (pp. 2240\u20132244).","DOI":"10.1109\/CDC.2000.914130"},{"issue":"9","key":"10.1016\/j.automatica.2026.113011_b41","doi-asserted-by":"crossref","first-page":"1555","DOI":"10.1109\/9.412626","article-title":"Diagnosability of discrete-event systems","volume":"40","author":"Sampath","year":"1995","journal-title":"IEEE Transactions on Automatic Control"},{"issue":"5","key":"10.1016\/j.automatica.2026.113011_b42","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1109\/TSMCA.2012.2227251","article-title":"Verification of modular diagnosability with local specifications for discrete-event systems","volume":"43","author":"Schmidt","year":"2013","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics: Systems"},{"key":"10.1016\/j.automatica.2026.113011_b43","series-title":"Introduction to the theory of computation","author":"Sipser","year":"2012"},{"key":"10.1016\/j.automatica.2026.113011_b44","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/j.automatica.2018.12.013","article-title":"Codiagnosability of discrete event systems revisited: A new necessary and sufficient condition and its applications","volume":"101","author":"Viana","year":"2019","journal-title":"Automatica"},{"issue":"2\u20133","key":"10.1016\/j.automatica.2026.113011_b45","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","article-title":"A new algorithm for optimal 2-constraint satisfaction and its implications","volume":"348","author":"Williams","year":"2005","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/j.automatica.2026.113011_b46","first-page":"105","article-title":"Diagnosability analysis of discrete event systems with autonomous components","volume":"Vol. 215","author":"Ye","year":"2010"},{"issue":"11","key":"10.1016\/j.automatica.2026.113011_b47","doi-asserted-by":"crossref","first-page":"5931","DOI":"10.1109\/TAC.2017.2699278","article-title":"On the decidability and complexity of diagnosability for labeled Petri nets","volume":"62","author":"Yin","year":"2017","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/j.automatica.2026.113011_b48","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.automatica.2017.06.013","article-title":"Verification complexity of a class of observational properties for modular discrete events systems","volume":"83","author":"Yin","year":"2017","journal-title":"Automatica"},{"issue":"9","key":"10.1016\/j.automatica.2026.113011_b49","doi-asserted-by":"crossref","first-page":"1491","DOI":"10.1109\/TAC.2002.802763","article-title":"Polynomial-time verification of diagnosability of partially observed discrete-event systems","volume":"47","author":"Yoo","year":"2002","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/j.automatica.2026.113011_b50","doi-asserted-by":"crossref","unstructured":"Zhou,\u00a0C., Kumar,\u00a0R., & Sreenivas,\u00a0R. S. (2008). Decentralized modular diagnosis of concurrent discrete event systems. In International workshop on discrete event systems (pp. 388\u2013393).","DOI":"10.1109\/WODES.2008.4605977"}],"container-title":["Automatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0005109826001950?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0005109826001950?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,5,22]],"date-time":"2026-05-22T10:56:19Z","timestamp":1779447379000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0005109826001950"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7]]},"references-count":50,"alternative-id":["S0005109826001950"],"URL":"https:\/\/doi.org\/10.1016\/j.automatica.2026.113011","relation":{},"ISSN":["0005-1098"],"issn-type":[{"value":"0005-1098","type":"print"}],"subject":[],"published":{"date-parts":[[2026,7]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Diagnosability verification for automata and Petri nets: Can we do better?","name":"articletitle","label":"Article Title"},{"value":"Automatica","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.automatica.2026.113011","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"113011"}}