Polynomials: From Dynamics to Databases
Massachusetts Institute of Technology
Abstract:
Polynomials in one variable form the objects of a very
interesting category, Poly, also known as the category of
containers in the sense of Abbott. Poly has four interacting
monoidal structures, and Ahman and Uustalu have shown that the
set of comonoids for one of them (composition of polynomials) is
precisely the set of categories up to isomorphism, a truly
remarkable result. Garner recently carried this further, showing
that bimodules between comonoids correspond to parametric right
adjoints between their associated copresheaf categories.
In this talk I'll explain how Poly is a natural setting for
talking about dynamical systems, or generalized Moore machines. A
Moore machine takes in input, updates its state, and produces
output. Moore machines can be wired together, feeding outputs of
one into inputs of another. One can see both the Moore machines
and the wiring diagrams in terms of maps in Poly, or more
precisely in the full subcategory of monomials. By generalizing
to all polynomials, we obtain generalized Moore machines where
the interface of each machine, as well as the wiring pattern
between these interfaces, can change based on the collective
states. Comonoids play an essential role here. Surprisingly, they
also play an essential role in the theory of databases, where we
can think of a database schema as a category (comonoid C in
Poly), its instances as C-copresheaves (C-coalgebras), and of
data migration functors as parametric right adjoints (bimodules).