Article ID Journal Published Year Pages File Type
427152 Information and Computation 2010 21 Pages PDF
Abstract

Covarieties of coalgebras are those classes of coalgebras for an endofunctor H on the category of sets that are closed under coproducts, subcoalgebras and quotients. Equivalently, covarieties are classes of H-coalgebras that can be presented by coequations. Adámek introduced a logic of coequations and proved soundness and completeness for all polynomial functors on the category of sets. Here this result is extended to accessible functors: given a presentation of an accessible functor H, simple deduction systems for coequations are formulated and it is shown that regularity of the presentation implies soundness and completeness of these deduction systems. The converse is true whenever H has a non-trivial terminal coalgebra. Also a method is found to obtain concrete descriptions of cofree (and thus terminal) coalgebras of accessible functors, and is applied to the finite and countable powerset functor as well as to the finite distribution functor.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics