×

Automata minimization: a functorial approach. (English) Zbl 1454.68069

There are various interpretations of the results of automata theory using category theory. Automata are interpreted as algebras [J. Adámek and V. Trnková, Automata and algebras in categories. Dordrecht etc.: Kluwer Academic Publishers (1990; Zbl 0698.18001); J. A. Goguen, Bull. Am. Math. Soc. 78, 777–783 (1972; Zbl 0277.18003); B. Jacobs and J. Rutten, Bull. EATCS 62, 222–259 (1997; Zbl 0880.68070); J. J. M. M. Rutten, Theor. Comput. Sci. 249, No. 1, 3–80 (2000; Zbl 0951.68038)]. This turned out to be useful [F. Bonchi et al., ACM Trans. Comput. Log. 15, No. 1, Article No. 3, 29 p. (2014; Zbl 1288.68174)] for understanding the Brzozowski minimization algorithm and the duality between reachability and observability going back to [M. A. Arbib and E. G. Manes, J. Pure Appl. Algebra 6, 313–344 (1975; Zbl 0323.18002); R. E. Kalman et al., Topics in mathematical system theory. New York etc.: McGraw-Hill Book Company (1969; Zbl 0231.49001)].
The paper under review takes a slightly different approach. The main idea of the paper is to consider an automaton as a functor from a category representing input words into a category representing a computation and output spaces.
Recall that a deterministic automaton \((Q, A, q_0, F, \delta)\) consists of a set of states \(Q\), an alphabet \(A\), an intial state \(q_0\in Q\), a set \(F\subseteq Q\) of final states, and a transition map \(\delta_a\) for every \(a\in A\).
Given a word \(a_1\ldots a_n\), the automaton accepts the word if \(\delta_{a_n}\circ \cdots \circ \delta_{a_1}(q_0)\in F\), and rejects it otherwise. Consider \(q_0\) as a map \(\mathsf{init}: 1= \{0\}\to Q\), that maps \(0\) to \(q_0\), and \(F\) as a map \(\mathsf{final}: Q\to 2=\{0, 1\}\), where \(1\) means ‘accept’ and \(0\) means ‘reject’. Then the semantics of the automaton is to associate to each word \(a_1\ldots a_n\) the map \(1\to 2\) defined by the composition \(\mathsf{final}\circ\delta_{a_n}\circ \cdots \circ\delta_{a_1}\circ \mathsf{init}\).
Let \(\mathcal{I}_{\mathsf{word}}\) be the free category generated by a graph consisting of three objects, \(\mathsf{in}\), \(\mathsf{states}\), \(\mathsf{out}\), with arrows \(\mathsf{in}\stackrel{\triangleright}\to \mathsf{states}\), \(\mathsf{states}\stackrel{a}\to \mathsf{states}\) for every \(a\in A\), and \(\mathsf{states}\stackrel{\triangleleft}\to \mathsf{out}\). We can consider the semantics of the automaton as a functor \(\mathcal{I}_{\mathsf{word}}\to \mathsf{Set}\) that sends the objects \(\mathsf{in}\) to \(1\) and \(\mathsf{out}\) to \(2\). Any morphism \(\mathsf{in} \to \mathsf{out}\) can be written as a composition \(\triangleleft w \triangleright\) for some \(w\in A^*\). The language can be considered as a map \(A^*\to \mathsf{Set}(1,2)\) that is viewed as a functor \(\mathcal O_{\mathsf{word}}\to \mathsf{Set}\) where \(\mathcal O_{\mathsf{word}}\subseteq \mathcal I_{\mathsf{word}}\) is the full subcategory such that \(\mathsf{Ob}(\mathcal O_{\mathsf{word}})=\{\mathsf{in}, \mathsf{out}\}\).
In general, \(\mathcal I\) is an arbitrary small category, and \(\mathcal O\) is a full subcategory of \(\mathcal I\). The embedding is denoted by \(\iota: \mathcal O\to \mathcal I\). A machine/automaton \(\mathcal A\) is a functor from \(\mathcal I\) to a category of outputs \(\mathcal C\).
The authors of the paper under review introduce the following concepts (Definition 2.1): A \(\mathcal C\)-language is a functor \(\mathcal L: \mathcal O \to \mathcal C\) and a \(\mathcal C\)-automaton is a functor \(\mathcal A: \mathcal I \to \mathcal C\). A \(\mathcal C\)-automaton \(\mathcal A\) accepts a \(\mathcal C\)-language \(\mathcal L\) when \(\mathcal A \circ \iota = \mathcal L\). \(\mathsf{Auto}(\mathcal L)\) is the subcategory of the functor category \([\mathcal I, \mathcal C]\) where (1) objects are \(\mathcal C\)-automata that accept \(\mathcal L\) and (2) arrows are natural transformations \(\alpha: \mathcal A \to \mathcal B\) so that the natural transformation \(\alpha\circ \iota= \mathsf{id}_{\mathcal L}\). Here, the natural transformation \(\alpha\circ \iota\) is defined by “Godement rules” \((\alpha\circ \iota)_{\omega}= \alpha_{\iota(\omega)}: \mathcal A(\iota(\omega))\to \mathcal B(\iota(\omega))\) for all \(\omega \in \mathsf{Ob}(\mathcal O)\).
Example 2.2 shows that deterministic automata are represented as functors valued in the category \(\mathsf{Set}\) of sets and functions, nondeterministic automata as functors valued in the category \(\mathsf{Rel}\) of sets and relations, while weighted automata over a semiring \(S\) as functors valued in the category of \(S\)-modules. The notions of language and of language accepted by an automaton are adapted along the same pattern.
Subsection 2.2 is devoted to the minimization of \(\mathcal C\)-automata. Let \(\mathcal K\) be a category with initial object \(I\) and final object \(F\) and let \((\mathcal E, \mathcal M)\) be a factorization system for \(\mathcal K\) in the sense of [Zbl 0323.18002]. For \(X, Y\in \mathsf{Ob}(\mathcal K)\), we say that \(X\) \((\mathcal E, \mathcal M)\)-divides \(Y\) if there are \(Z\in \mathsf{Ob}(\mathcal K)\) and morphisms \((X \twoheadleftarrow Z) \in \mathcal E\) and \((Z \rightarrowtail Y)\in \mathcal M\). An object \(M\in \mathsf{Ob}(\mathcal K)\) is called \((\mathcal E, \mathcal M)\)-minimal if it \((\mathcal E, \mathcal M)\)-divides all objects of \(\mathcal K\). There is an object denoted by \(\mathsf{Min}\) with the factorization \(I\twoheadrightarrow \mathsf{Min} \rightarrowtail F\) of the unique arrow \(I\to F\) by an \(\mathcal E\)-epimorphism and an \(\mathcal M\)-monomorphism. By Lemma 2.3, \(\mathsf{Min}\) is \((\mathcal E, \mathcal M)\)-minimal.
Let \(\mathcal K\) be the category \(\mathsf{Auto}(\mathcal L)\) of \(\mathcal C\)-automata accepting the language \(\mathcal L\). Assuming the existence of an initial and a final automaton for \(\mathcal L\) – denoted by \(\mathcal A^{\mathsf{init}}(\mathcal L)\) respectively \(\mathcal A^{\mathsf{final}}(\mathcal L)\) – we can define the minimal automaton \(\mathsf{Min}(\mathcal L)\) for the language \(\mathcal L\) as obtained via the factorization \[ \mathcal A^{\mathsf{init}}(\mathcal L) \twoheadrightarrow \mathsf{Min}(\mathcal L) \rightarrowtail \mathcal A^{\mathsf{final}}(\mathcal L). \]
In Section 2, the following sufficient conditions for the existence of an initial and a final \(\mathcal L\)-automaton are obtained (and even more).
Corollary 2.10. Assume \(\mathcal C\) is complete, cocomplete and has a factorization system, and let \(\mathcal L\) be a \(\mathcal C\)-language. Then the initial \(\mathcal L\)-automaton and the final \(\mathcal L\)-automaton exist and are given by the left respectively right Kan extensions of \(\mathcal L\) along \(\iota\). Furthermore, the minimal \(\mathcal C\)-automaton \(\mathsf{Min}(\mathcal L)\) accepting \(\mathcal L\) is obtained via the factorization \[ \mathsf{Lan}_{\iota}\mathcal L \twoheadrightarrow \mathsf{Min}(\mathcal L) \rightarrowtail \mathsf{Ran}_{\iota}\mathcal L. \]
The main result of Section 3, Lemma 3.4, shows how we can lift an adjunction between the output categories \(\mathcal C\) and \(\mathcal D\) to an adjunction between categories of automata that accept essentially the same language, admitting two equivalent representations in \(\mathcal C\) and \(\mathcal D\). This lifting accounts for several constructions in automata theory, determinization to start with. Indeed, determinization of automata can be understood via a lifting of the Kleisli adjunction between the categories \(\mathsf{Rel}\) and \(\mathsf{Set}\); and reversing nondeterministic automata can be understood via a lifting of the self-duality of \(\mathsf{Rel}\).
This structure is then used to explain some of the constructs in automata theory.
In Section 4, Theorem 4.5 is proved, which is devoted to the rephrasing of the minimization result for subsequential transducers due to C. Choffrut [Lect. Notes Comput. Sci. 71, 88–103 (1979; Zbl 0419.68086)]. The proof is carried out using the Kleisli category for the monad \(\mathcal T X = B^*\times X + 1\), where \(B\) is the output alphabet of the transducers.
Section 5 presents the second application, which consists in proving the correctness of the Brzozowski minimization algorithm for both deterministic and weighted automata. A weighted version of the Brzozowski minimization algorithm was described in [Zbl 1288.68174].
Section 6 shows how a syntactic monoid for a language can be obtained in the same spirit as a minimal automaton. For this purpose, the category representing finite words is replaced by a category suitable for representing biaction and monoid recognizers of languages.

MSC:

68Q70 Algebraic theory of languages and automata
18B20 Categories of machines, automata
PDF BibTeX XML Cite
Full Text: arXiv Link

References:

[1] Jir´ı Ad´amek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa. Well-pointed coalgebras.Logical Methods in Computer Science, 9(3), 2013. · Zbl 1272.18002
[2] Jiˇr´ı Ad´amek and Vˇera Trnkov´a.Automata and Algebras in Categories. 37. Springer Netherlands, New York, 1989.
[3] Jiˇr´ı Ad´amek, Filippo Bonchi, Mathias H¨ulsbusch, Barbara K¨onig, Stefan Milius, and Alexandra Silva. A coalgebraic perspective on minimization and determinization. InProceedings of the 15th International
[4] Michael A. Arbib and Ernest G. Manes. Adjoint machines, state-behavior machines, and duality.Journal of Pure and Applied Algebra, 6(3):313 - 344, 1975. · Zbl 0323.18002
[5] Edwin S. Bainbridge. Adressed machines and duality. InCategory Theory Applied to Computation and Control, volume 25 ofLecture Notes in Computer Science, pages 93-98. Springer, 1974.
[6] Nick Bezhanishvili, Clemens Kupke, and Prakash Panangaden.Minimization via Duality, pages 191-205. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. · Zbl 1361.68157
[7] Filippo Bonchi, Marcello M. Bonsangue, Helle Hvid Hansen, Prakash Panangaden, Jan J. M. M. Rutten, and Alexandra Silva. Algebra-coalgebra duality in Brzozowski’s minimization algorithm.ACM Trans. · Zbl 1288.68174
[8] Filippo Bonchi, Marcello M. Bonsangue, Jan J. M. M. Rutten, and Alexandra Silva. Brzozowski’s algorithm (co)algebraically. InLogic and Program Semantics, volume 7230 ofLecture Notes in Computer Science, pages 12-23. Springer, 2012. · Zbl 1354.68185
[9] C. Cassidy, Michel H´ebert, and Max G. Kelly. Reflective subcategories, localizations and factorization systems.Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics, 38(3):287-329, 1985. · Zbl 0573.18002
[10] Christian Choffrut. A generalization of Ginsburg and Rose’s characterization of G-S-M mappings. In ICALP, volume 71 ofLecture Notes in Computer Science, pages 88-103. Springer, 1979. · Zbl 0419.68086
[11] Christian Choffrut. Minimizing subsequential transducers: a survey.Theoretical Computer Science, 292(1):131 - 143, 2003. · Zbl 1063.68065
[12] Thomas Colcombet and Daniela Petri¸san. Automata in the category of glued vector spaces. InMFCS, volume 83 ofLIPIcs, pages 52:1-52:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
[13] Thomas Colcombet and Daniela Petri¸san. Automata minimization: a functorial approach. InCALCO, volume 72 ofLIPIcs, pages 8:1-8:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. · Zbl 1433.68222
[14] Mai Gehrke, Daniela Petri¸san, and Luca Reggio. The Sch¨utzenberger product for syntactic spaces. In ICALP, volume 55 ofLIPIcs, pages 112:1-112:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. · Zbl 1388.68193
[15] Joseph A. Goguen. Minimal realization of machines in closed categories.Bull. Amer. Math. Soc., 78(5):777-783, 09 1972. · Zbl 0277.18003
[16] Helle Hvid Hansen. Subsequential transducers: a coalgebraic perspective.Inf. Comput., 208(12):1368- 1397, 2010. · Zbl 1209.68297
[17] Bart Jacobs and Jan Rutten. A tutorial on (co)algebras and (co)induction.EATCS Bulletin, 62:62-222, 1997. · Zbl 0880.68070
[18] Rudolf E. Kalman, Peter L. Falb, and Michael A. Arbib.Topics in Mathematical System Theory. McGraw Hill Book Company, New York, Toronto, Sydney, 1969.
[19] Henning Kerstan, Barbara K¨onig, and Bram Westerbaan. Lifting adjunctions to coalgebras to (re)discover automata constructions. InCMCS, volume 8446 ofLecture Notes in Computer Science, pages 168-188. Springer, 2014. · Zbl 1360.68609
[20] Saunders MacLane.Categories for the Working Mathematician, volume 5 ofGraduate Texts in Mathematics. Springer-Verlag, New York, 1971. · Zbl 0705.18001
[21] Kimmo .I. Rosenthal. Quantaloids, enriched categories and automata theory.Appl Categor Struct, 3(279), 1995. · Zbl 0833.18002
[22] Jan J.M.M. Rutten. Universal coalgebra: a theory of systems.Theoretical Computer Science, 249(1):3 - 80, 2000. Modern Algebra. · Zbl 0951.68038
[23] Alexandra Silva, Filippo Bonchi, Marcello M. Bonsangue, and Jan J. M. M. Rutten. Generalizing determinization from automata to coalgebras.Logical Methods in Computer Science, 9(1), 2013. · Zbl 1262.18002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.