ENLARGEMENTS OF POLYNOMIAL COALGEBRAS
Robert Goldblatt · 2003
This paper continues a series [GolOlc,a,b] of articles on the equational logic and model theory of coalgebras for certain functors T: Set - Set on the category of sets. A T-coalgebra is a pair (A, () comprising a set A, thought of as a set of "states", and a function : A -> TA called the transition structure. We study the case of functors T that are polynomial, i.e. constructed from constant-valued functors and the identity functor by forming products, coproducts, and exponential functors with constant exponent. Many data structures and systems of interest to computer science - such as lists, streams, trees, automata, and classes in object-oriented programming languages - can be modelled as coalgebras for polynomial functors [Rei95, Jac96, Rut95, Rut00]. This has motivated the development of a theory of "universal coalgebra" [Rut95, Rut00], by analogy with, and categorically dual to, the study of abstract algebras