Accessible and Locally Accessible Categories
J. Adámek
Research in the structure of accessible categories has continued in two directions. One, in a colaboration with J. Rosický, concerned the ''dualization'' of the idea of pure subobject. This concept has turned out to play a central role in the theory of accessible categories. Whereas pure subobjects are defined as filtered colimits of split subobjects, pure quotients are filtered colimits of split quotients. Some properties of pure subobjects are found again in pure quotient. However, the crucial fact that every accessible category has enough pure subobjects does not have a direct analogy.The second direction, in colaboration with H.-E. Porst and L. Sousa, concerned presentability in categories of coalgebras and bialgebras. For example, deterministic systems, considered as coalgebras over polynomial functors, turn out to form locally finitely presentable categories, whereas nondeterminism ''spoils'' presentability, as examplified by finite-branching graphs (as coalgebras of the finite power-set functor): that category is not locally finitely presentable.
Coalgebraic Specification
J. Adámek
Coalgebras present a formalism for description of computations in various systems, where the role of a final coalgebra is to summarize all possible behaviours of systems of the same type. In particular, labelled transition systems as coalgebras of the power-set functor lead to the problem of describing the final coalgebra (which is a proper class) or its iterative approximations. The study of final coalgebras has turned out to be useful in explaining additional structures (e.g. complete partial orders, or complete metric speces) applied in the theory of computation.An element of a final coalgebra can be understood to be a ''coequation'' which a system satisfies iff no state of that system has that particular behaviour. Many important types of systems are coequationally specified, i.e., specified by a collection of coequations. E.g., labelled transition systems that are reflexive, or symmetric, etc. A general theory of covarieties, i.e., classes of coalgebras presented by coequations, has been developed in a colaboration of Hans-Eberhard Porst with J. Adámek.
Coalgebraic Approach to Iterative Theories
J. Adámek, S. Milius
An important topic in the theory of coalgebras is solution of recursive equations and (completely) iterative monads as an approach to the formalization of computations of data through a given program, taking into account that such computations are potentially infinite and abstracting away from the nature of external memory. Examples of such computations are evaluation in lazy functional languages, or computations on (potentially) infinite data structures like streams. There have been many algebraic approaches to infinite computations. Most of these work with models that require to consider additional (and always a bit arbitrary) structure like complete partial orders or complete metric spaces on them. In the 1970's this has led Calvin Elgot and his co-authors to study iterative and completely iterative theories, which are algebraic theories that admit unique solutions of ideal systems of recursive equations. The difference between iterative and completely iterative theories is that the former allow only solutions of finitary systems of equations whereas the latter do not have such a restriction. A principal result of Elgot et al. was a description of a free completely iterative theory over any signature of operation symbols. It is the theory formed by all infinite trees labelled in that signature.A coalgebraic approach makes it possible to study those theories in a conceptually clearer categorical setting. Our approach relies on the well-known fact that the (co-)algebra of infinite trees allows for unique solutions of guarded recursive equations. This turns out to be a special case of a completely general fact, based on the observation that the coalgebra of infinite trees is the final coalgebra of the corresponding polynomial functor. All this generalizes to coalgebras over an endofunctor (or, more generally, the coproduct of that endofunctor with a constant endofunctor) of an arbitrary category with finite coproducts. Moreover, it turns out that the (co-)algebras of infinite trees form a free completely iterative monad on the given polynomial functor. Again, the above freeness result of Elgot et al. is a special case of a completely general fact that every suitable endofunctor generates a free completely iterative monad.
Furthermore, we investigated a generalization of rational trees as solutions of finitary guarded recursive equations. These are of even greater interest for applications in computer science since infinite computations here are always given by a finite recursive description. In fact, rational trees over a signature were shown to be the free iterative theory over a signature by Elgot. Again, a coalgebraic approach lets us obtain this result in a conceptionally clearer way and in greater generality. Many endofunctors (i.e., all that satisfy a mild side condition) on a locally finitely presentable category (i.e. one in which it makes sense to speak about finiteness of objects) generate a rational monad, which is a submonad of the above mentioned free completely iterative monad just as the theory of rational trees forms a subtheory of the theory of all infinite trees. We also obtain a freeness result; the rational monad is free over the given endofunctor one starts with.