×

The dual equivalence of equations and coequations for automata. (English) Zbl 1333.68184

This article investigates deterministic (potentially infinite-state) automata from a category-theoretic perspective. The basis of each automaton, its transition system, is an algebra and a co-algebra. Adding an initial state preserves the algebra structure, but adding a set of final states only preserves the co-algebra structure. In the following, let \(A = (Q, \Sigma, \delta)\) be a transition system with (potentially infinite) sets \(Q\) and \(\Sigma\) and transition function \(\delta : Q \times \Sigma \to Q\). Each choice \(q \in Q\) of an initial state determines a unique homomorphism \(h_q : \Sigma^* \to Q\), namely the one that given an input \(w \in \Sigma^*\) assigns the state reached after reading \(w\) starting from \(q\) in the transition system \(A\). A set \(E\) of equations for \(A\) is defined to be a bisimulation equivalence \(E\) on \(\Sigma^*\) (i.e., an equivalence such that for every \((v, w) \in E\) also \((v\sigma, w\sigma) \in E\) for all \(\sigma \in \Sigma\)) such that \(h_q(v) = h_q(w)\) for all \((v, w) \in E\) and \(q \in Q\). In other words, if the words \(v\) and \(w\) are in relation, then no matter at which initial state we start we need to reach the same state processing \(v\) and \(w\). The transition structure \(\operatorname{free}(A)\) is the product of the automata \((A_q)_{q \in Q}\), where \(A_q\) is the transition structure \(A\) together with the initial state \(q\), factored by the kernel \(K\) of its reachability map. It is demonstrated that the kernel \(K\) is the largest set of equations for \(A\). Similarly, a set of co-equations is a subautomaton of the automaton of right languages such that the right language of each state \(q \in Q\) is contained for each choice of final states \(F \subseteq Q\). A co-product construction yields the automaton \(\operatorname{cofree}(A)\) representing the smallest set of co-equations for \(A\). Both constructions are actually functorial. Furthermore it is demonstrated that certain natural restrictions of \(\operatorname{free}(A)\) and \(\operatorname{cofree}(A)\) form a dual equivalence, and as a consequence a variant of Eilenberg’s variety theorem is obtained.
Although the paper uses category theory, the paper remains accessible to non-experts in category theory. All notions are carefully explained and should be understandable to graduate students of mathematics or theoretical computer science. Examples are provided for all major constructions and they illustrate the notions well. The constructions actually mirror well-known ones, like the construction of the syntactic monoid, so prior exposure to algebraic automata theory will help the reader.

MSC:

68Q70 Algebraic theory of languages and automata
18A30 Limits and colimits (products, sums, directed limits, pushouts, fiber products, equalizers, kernels, ends and coends, etc.)
18A32 Factorization systems, substructures, quotient structures, congruences, amalgams
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Eilenberg, S., Automata, Languages and Machines, vol. A, Pure and Applied Mathematics (1974), Academic Press · Zbl 0317.94045
[2] Eilenberg, S., Automata, Languages and Machines, vol. B, Pure and Applied Mathematics (1976), Academic Press · Zbl 0359.94067
[3] Rutten, J., Automata and coinduction (an exercise in coalgebra), (Sangiorgi, D.; de Simone, R., Proceedings of CONCUR’98. Proceedings of CONCUR’98, LNCS, vol. 1466 (1998)), 194-218 · Zbl 0940.68085
[4] Rutten, J., Universal coalgebra: a theory of systems, Theor. Comput. Sci., 249, 1, 3-80 (2000), fundamental study · Zbl 0951.68038
[5] Sakarovitch, J., Elements of Automata Theory (2009), Cambridge University Press
[6] Pin, J.-E., Mathematical Foundations of Automata Theory (2014)
[7] Birkhoff, G., On the structure of abstract algebras, Math. Proc. Camb. Philos. Soc., 31, 433-454 (1935) · Zbl 0013.00105
[8] Arbib, M.; Zeiger, H., On the relevance of abstract algebra to control theory, Automatica, 5, 589-606 (1969) · Zbl 0199.49303
[9] Arbib, M.; Manes, E., Adjoint machines, state-behaviour machines, and duality, J. Pure Appl. Algebra, 6, 313-344 (1975) · Zbl 0323.18002
[10] Kalman, R., On the general theory of control systems, IRE Trans. Autom. Control, 4, 3, 110-111 (1959)
[11] Kalman, R. E.; Falb, P. L.; Arbib, M. A., Topics in Mathematical Systems Theory (1969), McGraw Hill · Zbl 0231.49001
[12] Bonchi, F.; Bonsangue, M.; Rutten, J.; Silva, A., Brzozowski’s algorithm (co)algebraically, (Constable, R.; Silva, A., Logic and Program Semantics. Logic and Program Semantics, LNCS, vol. 7230 (2012)), 12-23 · Zbl 1354.68185
[14] Brzozowski, J., Derivatives of regular expressions, J. ACM, 11, 4, 481-494 (1964) · Zbl 0225.94044
[16] Rabin, M. O.; Scott, D., Finite automata and their decision problems, IBM J. Res. Dev., 3, 2, 114-125 (1959) · Zbl 0158.25404
[17] Gehrke, M., Duality and recognition, (Sankowski, P.; Murlak, F., Mathematical Foundations of Computer Science. Mathematical Foundations of Computer Science, LNCS, vol. 6907 (2011)), 3-18 · Zbl 1343.68158
[18] Almeida, J., Residually finite congruences and quasi-regular subsets in uniform algebras, Port. Math., 46, 3, 313-328 (1989) · Zbl 0688.08001
[19] Almeida, J., Finite Semigroups and Universal Algebra, Series in Algebra (1994), World Scientific
[20] Pippenger, N., Regular languages and stone duality, Theory Comput. Syst., 30, 2, 121-134 (1997) · Zbl 0870.68092
[21] Gehrke, M., Stone duality and the recognisable languages over an algebra, (Kurz, A.; etal., Algebra and Coalgebra in Computer Science. Algebra and Coalgebra in Computer Science, CALCO 2009. Algebra and Coalgebra in Computer Science. Algebra and Coalgebra in Computer Science, CALCO 2009, LNCS, vol. 5728 (2009)), 236-250 · Zbl 1239.68047
[22] Gehrke, M.; Grigorieff, S.; Pin, J.-E., Duality and equational theory of regular languages, (Proceedings ICALP. Proceedings ICALP, LNCS, vol. 5126 (2008)), 246-257 · Zbl 1165.68049
[23] Manes, E.; Arbib, M., Algebraic Approaches to Program Semantics, The AKM Series in Theoretical Computer Science (1986), Springer: Springer New York · Zbl 0599.68008
[24] Conway, J., Regular Algebra and Finite Machines, Dover Books on Mathematics (2012), Dover Publications
[25] Kleene, S., Representation of events in nerve nets and finite automata, (McCarthy, J.; Shannon, C. E.; Ashby, W. R., Automata Studies (1956), Princeton Univ. Press), 3-41
[26] Dekkers, M., Stone duality. An application in the theory of formal languages (December 2008), Radboud Universiteit Nijmegen: Radboud Universiteit Nijmegen The Netherlands, master’s thesis
[27] Schützenberger, M., On finite monoids having only trivial subgroups, Inf. Control, 8, 2, 190-194 (1965) · Zbl 0131.02001
[28] Simon, I., Piecewise testable events, (Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages (1975), Springer-Verlag: Springer-Verlag London, UK), 214-222 · Zbl 0316.68034
[29] Pin, J.-E., A variety theorem without complementation, Russ. Math. (Izv. VUZ), 39, 80-90 (1995)
[30] Straubing, H., On logical descriptions of regular languages, (Rajsbaum, S., LATIN 2002: Theoretical Informatics. LATIN 2002: Theoretical Informatics, Lecture Notes in Computer Science, vol. 2286 (2002), Springer: Springer Berlin/Heidelberg), 528-538 · Zbl 1059.03034
[31] Ésik, Z.; Ito, M., Temporal logic with cyclic counting and the degree of aperiodicity of finite automata, Acta Cybern., 16, 1, 1-28 (2003) · Zbl 1027.68074
[32] Reis, C. M.; Shyr, H. J., Some properties of disjunctive languages on a free monoid, Inf. Control, 37, 3, 334-344 (1978) · Zbl 0376.68044
[33] Grillet, P., Semigroups: an Introduction to the Structure Theory (1995), Marcel Dekker, Inc.: Marcel Dekker, Inc. New York · Zbl 0830.20079
[34] Kogalovskiĭ, S. P., On Birkhoff’s theorem, Usp. Mat. Nauk, 20, 5, 206-207 (1965)
[35] Neumann, H., Varieties of Groups, Ergeb. Math. Ihrer Grenzgeb. (1967), Springer-Verlag · Zbl 0149.26704
[36] Grätzer, G., Universal Algebra, Mathematics and Statistics (2008), Springer · Zbl 1143.08001
[37] Pin, J.-É., Varieties of Formal Languages (1986), North Oxford/Plenum: North Oxford/Plenum London/New York, translation: Variétés de langages formels, Masson, 1984 · Zbl 0632.68069
[38] Bonchi, F.; Pous, D., Checking NFA equivalence with bisimulations up to congruence, (Proc. POPL (2013)), 457-468 · Zbl 1301.68169
[39] Ballester-Bolinches, A.; Pin, J.-É.; Soler-Escrivà, X., Formations of finite monoids and formal languages: Eilenberg’s theorem revisited, Forum Math., 26, 6, 1731-1761 (2012) · Zbl 1310.20054
[40] Reiterman, J., The Birkhoff theorem for finite algebras, Algebra Univers., 14, 1, 1-10 (1982) · Zbl 0484.08007
[41] Almeida, J., Profinite semigroups and applications, (Structural Theory of Automata, Semigroups, and Universal Algebra (2003)), 7-18
[42] Rhodes, J.; Steinberg, B., The \(q\)-Theory of Finite Semigroups, Springer Monographs in Mathematics (2009), Springer: Springer New York · Zbl 1186.20043
[43] Roumen, F., Canonical automata via duality (2011), Radboud Universiteit Nijmegen: Radboud Universiteit Nijmegen the Netherlands, Master’s thesis
[44] Rutten, J.; Ballester-Bolinches, A.; Cosme-Llópez, E., Varieties and covarieties of languages (preliminary version), (Kozen, D.; Mislove, M., Proceedings of MFPS XXIX. Proceedings of MFPS XXIX, Electron. Notes Theor. Comput. Sci., vol. 298 (2013)), 7-28 · Zbl 1334.68139
[45] Bezhanishvili, N.; Kupke, C.; Panangaden, P., Minimization via duality, (Ong, C.-H. L.; de Queiroz, R. J.G. B., WoLLIC. WoLLIC, LNCS, vol. 7456 (2012)), 191-205 · Zbl 1361.68157
[46] Adámek, J.; Milius, S.; Myers, R.; Urbat, H., Generalized Eilenberg theorem, I: local varieties of languages, (Muscholl, A., Foundations of Software Science and Computation Structures. Foundations of Software Science and Computation Structures, LNCS, vol. 8412 (2014)), 366-380 · Zbl 1407.68314
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.