We prove that the iterative construction of initial algebras converges for endofunctors F of many-sorted sets whenever F has an initial algebra. In the case of one-sorted sets, the convergence takes n steps where n is either an infinite regular cardinal or is at most 3. Dually, the existence of a many-sorted terminal coalgebra implies that the iterative construction of a terminal coalgebra converges. Moreover, every endofunctor with a fixed-point pair larger than the number of sorts is proved to have a terminal coalgebra. As demonstrated by James Worell, the number of steps here need not be a cardinal even in the case of a single sort: it is ω + ω for the finite power-set functor. The above results do not hold for related categories, such as graphs: we present non-constructive initial algebras and terminal coalgebras.

Accessible set functors can be presented by signatures and equations as quotients of polynomial functors.We determine how preservation of pullbacks and other related properties (often applied in coalgebra) are re ected in the structure of the system of equations.

Two problems are said to be polynomially equivalent if each is polynomially reducible to the other. A problem is said to be isomorphism-complete if it is polynomially equivalent to the graph isomorphism problem. We prove that the isomorphism problem in any variety of unary algebras is either isomorphism-complete, or solvable in polynomial time. We formulate a condition C under which the isomorphism problem in a variety V of unary algebras can be solved in polynomial time. We present an algorithm that can be applied to any pair of unary algebras with the same number of operations and decides whether the algebras are isomorphic or not in $O(n^3 )$ time, provided one of them belongs to a variety satisfying C. The validity of the last condition is tested by the algorithm in linear time.