×

On minimal coalgebras. (English) Zbl 1144.18002

Summary: We define an out-degree for \(F\)-coalgebras and show that the coalgebras of outdegree at most \(\kappa\) form a covariety. As a subcategory of all \(F\)-coalgebras, this class has a terminal object, which for many problems can stand in for the terminal \(F\)-coalgebra, which need not exist in general. As examples, we derive structure theoretic results about minimal coalgebras, showing that, for instance minimization of coalgebras is functorial, that products of finitely many minimal coalgebras exist and are given by their largest common subcoalgebra, that minimal subcoalgebras have no inner endomorphisms and show how minimal subcoalgebras can be constructed from Moore-automata. Since the elements of minimal subcoalgebras must correspond uniquely to the formulae of any logic characterizing observational equivalence, we give in the last section a straightforward and self-contained account of the coalgebraic logic of D. Pattinson [Notre Dame J. Formal Logic 45, 19–33 (2004; Zbl 1088.03031)] and L. Schröder [Lect. Notes Comput. Sci. 3441, 440–454 (2005; Zbl 1119.03015)], which we believe is simpler and more direct than the original exposition.

MSC:

18B20 Categories of machines, automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
16W30 Hopf algebras (associative rings and algebras) (MSC2000)
03B70 Logic in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aczel, P., Mendler, N.: A final coalgebra theorem. In: Pitt, D.H. et al. (eds.) Proceedings Category Theory and Computer Science, Lecture Notes in Computer Science, pp. 357–365. Springer (1989)
[2] Adámek, J., Herrlich, H., Strecker, G.E.: Abstract and Concrete Categories. John Wiley & Sons (1990) · Zbl 0695.18001
[3] Gumm, H.P.: Elements of the General Theory of Coalgebras. LUATCS 99, Rand Afrikaans University, Johannesburg, South Africa (1999)
[4] Gumm, H.P.: From T-coalgebras to filter structures and transition systems. In: Fiadeiro, D.H. et al. (eds.) Algebra and Coalgebra in Computer Science, vol. 3629 of Lecture Notes in Computer Science, pp. 194–212. Springer (2005) · Zbl 1151.18001
[5] Gumm, H.P., Schröder, T.: Products of coalgebras. Algebra Universalis 46, 163–185 (2001) · Zbl 1061.18005 · doi:10.1007/PL00000334
[6] Gumm, H.P., Schröder, T.: Coalgebras of bounded type. Math. Structures Comput. Sci. 12, 565–578 (2002) · Zbl 1011.08009 · doi:10.1017/S0960129501003590
[7] Gumm, H.P., Schröder, T.: Types and coalgebraic structure. Algebra Universalis 53, 229–252 (2005) · Zbl 1086.08002 · doi:10.1007/s00012-005-1888-2
[8] Hennessy, M., Milner, R.: Algebraic laws for nondeterminism and concurrency. J. Assoc. Comput. Mach. 32, 137–161 (1985) · Zbl 0629.68021
[9] Ihringer, Th., Gumm, H.P.: Allgemeine Algebra. Heldermann Verlag (2003)
[10] Kianpi, M., Jugnia, C.N.: A simplification functor for coalgebras. Int. J. Math. Math. Sci. (2006) · Zbl 1130.68056
[11] Koubek, V.: Set functors. Commun. Math. Univ. Carolinae 12(1), 175–195 (1971) · Zbl 0217.06803
[12] Manes, E.G.: Implementing collection classes with monads. Math. Structures Comput. Sci. 8, 231–276 (1998) · Zbl 0916.68016 · doi:10.1017/S0960129598002515
[13] Pattinson, D.: Expressive logics for coalgebras via terminal sequence induction. Notre Dame J. Formal Log. 45, 19–33 (2004) · Zbl 1088.03031 · doi:10.1305/ndjfl/1094155277
[14] Rutten, J.J.M.M.: Automata and coinduction (an exercise in coalgebra). In: Sangiorigi, D., de Simone, R. (eds.) Proceedings of CONCUR ’98, number 1466 in LNCS, pp. 194–218 (1998) · Zbl 0940.68085
[15] Rutten, J.J.M.M.: Universal coalgebra: a theory of systems. Theor. Comp. Sci. 249(1), 3–80 (2000) · Zbl 0951.68038 · doi:10.1016/S0304-3975(00)00056-6
[16] Schröder, L.: Expressivity of coalgebraic modal logic: the limits and beyond. In: Sassone, V., (ed.) Foundations of Software Science and Computation Structures (FOSSACS), Lecture Notes in Computer Science, pp. 440–454. Springer (2005) · Zbl 1119.03015
[17] Smyth, M.B., Plotkin, G.D.: The category-theoretic solution of recursive domain equations. SIAM J. Comput. 11(4), 761–783 (1982) · Zbl 0493.68022 · doi:10.1137/0211062
[18] Trnková, V.: On descriptive classification of set-functors I. Commun. Math. Univ. Carolinae 12(1), 323–352 (1971) · Zbl 0232.18004
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.