{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:04:57Z","timestamp":1767337497557,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,2,1]],"date-time":"2014-02-01T00:00:00Z","timestamp":1391212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004794","name":"Centre National de la Recherche Scientifique","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004794","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.021.231"],"award-info":[{"award-number":["639.021.231"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["SFRH\/BPD\/71956\/2010 and FCOMP-01-0124-FEDER-020537 (program COMPETE)"],"award-info":[{"award-number":["SFRH\/BPD\/71956\/2010 and FCOMP-01-0124-FEDER-020537 (program COMPETE)"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2014,2]]},"abstract":"<jats:p>We give a new presentation of Brzozowski's algorithm to minimize finite automata using elementary facts from universal algebra and coalgebra and building on earlier work by Arbib and Manes on a categorical presentation of Kalman duality between reachability and observability. This leads to a simple proof of its correctness and opens the door to further generalizations. Notably, we derive algorithms to obtain minimal language equivalent automata from Moore nondeterministic and weighted automata.<\/jats:p>","DOI":"10.1145\/2490818","type":"journal-article","created":{"date-parts":[[2014,3,4]],"date-time":"2014-03-04T13:24:59Z","timestamp":1393939499000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Algebra-coalgebra duality in brzozowski's minimization algorithm"],"prefix":"10.1145","volume":"15","author":[{"given":"Filippo","family":"Bonchi","sequence":"first","affiliation":[{"name":"ENS Lyon, Universit\u00e9 de Lyon LIP (UMR 5668), France"}]},{"given":"Marcello M.","family":"Bonsangue","sequence":"additional","affiliation":[{"name":"LIACS - Leiden University, The Netherlands"}]},{"given":"Helle H.","family":"Hansen","sequence":"additional","affiliation":[{"name":"Radboud University Nijmegen, The Netherlands"}]},{"given":"Prakash","family":"Panangaden","sequence":"additional","affiliation":[{"name":"McGill University, Quebec, Canada"}]},{"given":"Jan J. M. M.","family":"Rutten","sequence":"additional","affiliation":[{"name":"Centrum Wiskunde &amp; Informatica, Amsterdam, The Netherlands"}]},{"given":"Alexandra","family":"Silva","sequence":"additional","affiliation":[{"name":"Radboud University Nijmegen, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2014,3,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28729-9_4"},{"key":"e_1_2_1_2_1","volume-title":"Strecker","author":"Ad\u00e1mek Jir\u00ed","year":"2009","unstructured":"Jir\u00ed Ad\u00e1mek , Horst Herrlich , and George E . Strecker . 2009 . Abstract and Concrete Categories - The Joy of Cats. Dover Publications . Jir\u00ed Ad\u00e1mek, Horst Herrlich, and George E. Strecker. 2009. Abstract and Concrete Categories - The Joy of Cats. Dover Publications."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28729-9_6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0005-1098(69)90026-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1016026"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(75)90028-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1975.11993918"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972700024412"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90012-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(80)90090-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"N.\n      Bezhanishvili P.\n      Panangaden and \n      C.\n      Kupke\n  . \n  2012\n  . Minimization via duality. In Proceedings of the 19th Workshop on Logic Language Information on Computation (WoLLIC'12). L. Ong and R. de Queiroz Eds. Lecture Notes in Computer Science vol. \n  7456 Springer 191--205.  N. Bezhanishvili P. Panangaden and C. Kupke. 2012. Minimization via duality. In Proceedings of the 19th Workshop on Logic Language Information on Computation (WoLLIC'12). L. Ong and R. de Queiroz Eds. Lecture Notes in Computer Science vol. 7456 Springer 191--205.","DOI":"10.1007\/978-3-642-32621-9_14"},{"volume-title":"Proceedings of the 4th International Conference on Foundations of Software Sciences and Computational Structure (FoSSaCS)","author":"Bidoit Michel","key":"e_1_2_1_12_1","unstructured":"Michel Bidoit , Rolf Hennicker , and Alexander Kurz . 2001. On the duality between observability and reachability . In Proceedings of the 4th International Conference on Foundations of Software Sciences and Computational Structure (FoSSaCS) . Furio Honsell and Marino Miculan Eds., Lecture Notes in Computer Science, vol. 2030 , Springer , 72--87. Michel Bidoit, Rolf Hennicker, and Alexander Kurz. 2001. On the duality between observability and reachability. In Proceedings of the 4th International Conference on Foundations of Software Sciences and Computational Structure (FoSSaCS). Furio Honsell and Marino Miculan Eds., Lecture Notes in Computer Science, vol. 2030, Springer, 72--87."},{"key":"e_1_2_1_13_1","volume-title":"Foundations of Software Science and Computational Structures - Proceedings of the 15th International Conference (FOSSACS'12)","volume":"7213","author":"Birkedal Lars","year":"2012","unstructured":"Lars Birkedal , Ed. 2012 . Foundations of Software Science and Computational Structures - Proceedings of the 15th International Conference (FOSSACS'12) . Lecture Notes in Computer Science , vol. 7213 , Springer. Lars Birkedal, Ed. 2012. Foundations of Software Science and Computational Structures - Proceedings of the 15th International Conference (FOSSACS'12). Lecture Notes in Computer Science, vol. 7213, Springer."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2340820.2340823"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.12.002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422085.2422092"},{"key":"e_1_2_1_17_1","series-title":"MRI Symposia Series","volume-title":"Mathematical Theory of Automata","author":"Brzozowski Janusz A.","unstructured":"Janusz A. Brzozowski . 1962. Canonical regular expressions and minimal state graphs for definite events . In Mathematical Theory of Automata , MRI Symposia Series , vol. 12 , Polytechnic Press , Polytechnic Institute of Brooklyn, 529--561. Janusz A. Brzozowski. 1962. Canonical regular expressions and minimal state graphs for definite events. In Mathematical Theory of Automata, MRI Symposia Series, vol. 12, Polytechnic Press, Polytechnic Institute of Brooklyn, 529--561."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2032366.2032377"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Prague Stringology Conference (PSC'02)","author":"Champarnaud J.-M.","year":"2002","unstructured":"J.-M. Champarnaud , A. Khorsi , and T. Parantho\u00ebn . 2002. Split and Join for Minimizing: Brzozowskis algorithm . In Proceedings of the Prague Stringology Conference (PSC'02) . M. Bal\u00edk and M. Sim\u00e1nek Eds., Number DC- 2002 -03 in Report. 96--104. J.-M. Champarnaud, A. Khorsi, and T. Parantho\u00ebn. 2002. Split and Join for Minimizing: Brzozowskis algorithm. In Proceedings of the Prague Stringology Conference (PSC'02). M. Bal\u00edk and M. Sim\u00e1nek Eds., Number DC-2002-03 in Report. 96--104."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111009070"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1812941.1812963"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_21"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1972-13032-5"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1959.1104873"},{"key":"e_1_2_1_25_1","unstructured":"R. E. Kalman P. L. Falb and M. A. Arbib. 1969. Topics in Mathematical Systems Theory. McGraw Hill.  R. E. Kalman P. L. Falb and M. A. Arbib. 1969. Topics in Mathematical Systems Theory. McGraw Hill."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/256167.256195"},{"key":"e_1_2_1_27_1","volume-title":"On the coalgebraic theory of kleene algebra with tests. Tech. rep. Computing and Information Science","author":"Kozen Dexter","year":"1813","unstructured":"Dexter Kozen . 2008. On the coalgebraic theory of kleene algebra with tests. Tech. rep. Computing and Information Science , Cornell University . http:\/\/hdl.handle.net\/ 1813 \/10173. Dexter Kozen. 2008. On the coalgebraic theory of kleene algebra with tests. Tech. rep. Computing and Information Science, Cornell University. http:\/\/hdl.handle.net\/1813\/10173."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(63)90290-0"},{"key":"e_1_2_1_29_1","unstructured":"F. Roumen. 2011. Canonical automata via duality. Unpublished note.  F. Roumen. 2011. Canonical automata via duality. Unpublished note."},{"volume-title":"Fourier Analysis on Groups","author":"Rudin Walter","key":"e_1_2_1_30_1","unstructured":"Walter Rudin . 1962. Fourier Analysis on Groups . John Wiley and Sons . Walter Rudin. 1962. Fourier Analysis on Groups. John Wiley and Sons."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00056-6"},{"volume-title":"Elements of Automata Theory","author":"Sakarovitch Jacques","key":"e_1_2_1_32_1","unstructured":"Jacques Sakarovitch . 2009. Elements of Automata Theory . Cambridge University Press . Jacques Sakarovitch. 2009. Elements of Automata Theory. Cambridge University Press."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(61)80020-X"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Kamal Lodaya and Meena Mahajan, Eds., LIPIcs","volume":"8","author":"Silva Alexandra","unstructured":"Alexandra Silva , Filippo Bonchi , Marcello M. Bonsangue , and Jan J. M. M. Rutten. 2010. Generalizing the powerset construction, coalgebraically . In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Kamal Lodaya and Meena Mahajan, Eds., LIPIcs , vol. 8 , Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 272--283. Alexandra Silva, Filippo Bonchi, Marcello M. Bonsangue, and Jan J. M. M. Rutten. 2010. Generalizing the powerset construction, coalgebraically. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Kamal Lodaya and Meena Mahajan, Eds., LIPIcs, vol. 8, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 272--283."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11591191_28"},{"key":"e_1_2_1_36_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 5th International Conference on Implementation and Application of Automation (CIAA). Sheng Yu and Andrei Paun, Eds.","author":"Watson Bruce W.","unstructured":"Bruce W. Watson . 2000. Directly Constructing Minimal DFAs: Combining two algorithms by Brzozowski . In Proceedings of the 5th International Conference on Implementation and Application of Automation (CIAA). Sheng Yu and Andrei Paun, Eds. , Lecture Notes in Computer Science , vol. 2088 , Springer , 311--317. Bruce W. Watson. 2000. Directly Constructing Minimal DFAs: Combining two algorithms by Brzozowski. In Proceedings of the 5th International Conference on Implementation and Application of Automation (CIAA). Sheng Yu and Andrei Paun, Eds., Lecture Notes in Computer Science, vol. 2088, Springer, 311--317."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2490818","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2490818","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:36Z","timestamp":1750232076000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2490818"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["10.1145\/2490818"],"URL":"https:\/\/doi.org\/10.1145\/2490818","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2014,2]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}