Filippo Bonchi
Skip Abstract Section
Abstract
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.
- Jirí Adámek, Filippo Bonchi, Mathias Hülsbusch, Barbara König, Stefan Milius, and Alexandra Silva. 2012a. A coalgebraic perspective on minimization and determinization. In Proceedings of the 15th International Conference on Foundation of Software Sciences and Computational Structures (FOSSACS'12). Lars Birkedal, Ed. Lecture Notes in Computer Science, vol. 7213, Springer-Verlag, Berlin, 58--73. Google Scholar
Digital Library
- Jirí Adámek, Horst Herrlich, and George E. Strecker. 2009. Abstract and Concrete Categories - The Joy of Cats. Dover Publications.Google Scholar
- Jirí Adámek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa. 2012b. Well-pointed coalgebras (extended abstract). In Proceedings of the 15th International Conference on Foundation of Software Sciences and Computational Structures (FOSSACS'12). Lars Birkedal, Ed. Lecture Notes in Computer Science, vol. 7213, Springer-Verlag, Berlin, 89--103. Google ScholarDigital Library
- M. A. Arbib and H. P. Zeiger. 1969. On the relevance of abstract algebra to control theory. Automatica 5, 589--606. Google ScholarDigital Library
- M. A. Arbib and E. G. Manes. 1974. Machines in a category: An expository introduction. SIAM Rev. 16, 163--192.Google ScholarDigital Library
- Michael A. Arbib and Ernest G. Manes. 1975a. Adjoint machines, state-behavior machines, and duality. J. Pure Appl. Algebra 6, 3, 313--344.Google ScholarCross Ref
- M. A. Arbib and E. G. Manes. 1975b. Extensions of semilattices. Amer. Math. Month. 82, 7, 744--746.Google ScholarCross Ref
- M. A. Arbib and E. G. Manes. 1975c. Fuzzy machines in a category. Bullet. Australian Math. Soci. 13, 2, 169--210.Google ScholarCross Ref
- Michael A. Arbib and Ernest G. Manes. 1980a. Foundations of system theory: The Hankel MAtrix. J. Comput. Syst. Sci. 20, 330--378.Google ScholarCross Ref
- Michael A. Arbib and Ernest G. Manes. 1980b. Machines in a category. J. Pure Appl. Algebra 19, 9--20.Google ScholarCross Ref
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Filippo Bonchi, Marcello M. Bonsangue, Jan J. M. M. Rutten, and Alexandra Silva. 2012a. Brzozowski's algorithm (co)algebraically. In Logic and Program Semantics, Robert L. Constable and Alexandra Silva, Eds., Lecture Notes in Computer Science, vol. 7230, Springer, 12--23. Google ScholarDigital Library
- Filippo Bonchi, Marcello M. Bonsangue, Michele Boreale, Jan J. M. M. Rutten, and Alexandra Silva. 2012. A coalgebraic perspective on linear weighted automata. Inf. Comput. 211, 77--105. Google ScholarDigital Library
- Marcello M. Bonsangue, Stefan Milius, and Alexandra Silva. 2013. Sound and complete axiomatisations of coalgebraic language equivalence. ACM Trans. Comput. Logic 14, 1. Google ScholarDigital Library
- 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.Google Scholar
- Giusi Castiglione, Antonio Restivo, and Marinella Sciortino. 2011. Nondeterministic Moore Automata and Brzozowski's Algorithm. In Proceedings of the 16th International Conference on Implementation and Application of Automata (CIAA). Béatrice Bouchou-Markhoff, Pascal Caron, Jean-Marc Champarnaud, and Denis Maurel Eds., Lecture Notes in Computer Science, vol. 6807, Springer, 88--99. Google ScholarDigital Library
- J.-M. Champarnaud, A. Khorsi, and T. Paranthoën. 2002. Split and Join for Minimizing: Brzozowskis algorithm. In Proceedings of the Prague Stringology Conference (PSC'02). M. Balík and M. Simánek Eds., Number DC-2002-03 in Report. 96--104.Google Scholar
- Z. Ézik and A. Maletti. 2011. The category of simulations for weighted tree automata. Int. J. Found. Comput. Sci. 22, 8, 1845--1859.Google ScholarCross Ref
- Mai Gehrke. 2009. Stone duality and the recognisable languages over an algebra. In Proceedings of the 3rd International Conference on Algebra and Coalgebra in Computer Science (CALCO). Alexander Kurz, Marina Lenisa, and Andrzej Tarlecki, Eds., Lecture Notes in Computer Science, vol. 5728, Springer, 236--250. Google ScholarDigital Library
- Mai Gehrke, Serge Grigorieff, and Jean-Eric Pin. 2008. Duality and equational theory of regular languages. In Proceedings of the 35th International Colloquium on Autometa, Language and Programming (ICALP). Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, Eds., Lecture Notes in Computer Science, vol. 5126, Springer, 246--257. Google ScholarDigital Library
- J. Goguen. 1972. Minimal realization of machines in closed categories. Bull. Amer. Math. Soc. 78, 5, 777--783.Google ScholarCross Ref
- R. Kalman. 1959. On the general theory of control systems. IRE Trans. Autom. Control 4, 3, 110.Google ScholarCross Ref
- R. E. Kalman, P. L. Falb, and M. A. Arbib. 1969. Topics in Mathematical Systems Theory. McGraw Hill.Google Scholar
- Dexter Kozen. 1997. Kleene algebra with tests. ACM Trans. Program. Lang. Syst. 19, 3, 427--443. Google ScholarDigital Library
- 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.Google Scholar
- Michael O. Rabin. 1963. Probabilistic automata. Inform. Control 6, 3, 230--245.Google ScholarCross Ref
- F. Roumen. 2011. Canonical automata via duality. Unpublished note.Google Scholar
- Walter Rudin. 1962. Fourier Analysis on Groups. John Wiley and Sons.Google Scholar
- Jan J. M. M. Rutten. 2000. Universal coalgebra: A theory of systems. Theor. Comput. Sci. 249, 1, 3--80. Google ScholarDigital Library
- Jacques Sakarovitch. 2009. Elements of Automata Theory. Cambridge University Press. Google ScholarDigital Library
- Marcel Paul Schützenberger. 1961. On the definition of a family of automata. Inform. Control 4, 2--3, 245--270.Google ScholarCross Ref
- 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.Google Scholar
- D. Tabakov and M. Y. Vardi. 2005. Experimental evaluation of classical automata constructions. In Proceedings of the 12th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR). G. Sutcliffe and A. Voronkov Eds., Lecture Notes in Artificial Intelligence, vol. 3835, Springer, 396--411. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- James Michael Worthington. 2009. Automata, representations, and proofs. Ph.D. thesis, Cornell University, Ithaca, NY.Google Scholar
Index Terms
- Algebra-coalgebra duality in brzozowski's minimization algorithm
Recommendations
The dual equivalence of equations and coequations for automata
The transition structure α : X X A of a deterministic automaton with state set X and with inputs from an alphabet A can be viewed both as an algebra and as a coalgebra. We use this algebra-coalgebra duality as a common perspective for the study of ...
Varieties and Covarieties of Languages (Extended Abstract)
Because of the isomorphism (XxA)->X@?X->(A->X), the transition structure of a deterministic automaton with state set X and with inputs from an alphabet A can be viewed both as an algebra and as a coalgebra. This algebra-coalgebra duality goes back to ...
Bisimulation Minimisation of Weighted Automata on Unranked Trees
Several models of automata are available that operate unranked trees. Two well-known examples are the stepwise unranked tree automaton (suta) and the parallel unranked tree automaton (puta). By adding a weight, taken from some semiring, to every ...
Comments