Abstract

The microcosm principle is a terminology coined by Baez and Dolan to describe a phenomenon where a category C and its object X \in C both have the same algebraic structure, i.e. an inner algebra X residing in an outer algebra C. A classic example is “a monoid object in a monoidal category.”

In this talk I demonstrate another example—arising from process theory—carried by “the final coalgebra in a category of coalgebras.” Here the shared algebraic structure is that of some process algebra. This categorical view brings new insight to the study of systems as coalgebras which are composed to yield a larger system—via a component calculus. Our main result is a general compositionality theorem: the behavior of a composed system is determined by its constituent systems (components).

I will also discuss the relationship to semantics of functional programming. A suitable axiomatization of Hughes’ notion of arrow yields Freyd categories as models when it is interpreted in Sets; we present its model in CAT that uses coalgebras, where the axiomatization plays a role of a component calculus. Again compositionality is for free. I also wish to mention recent work where a GSOS specification is canonically turned into a component calculus, from which we can derive parallel composition S||T of two LTSs, replication !S of an LTS S , etc.

This talk is based on joint work with Chris Heunen (Oxford), Bart Jacobs (Nijmegen) and Ana Sokolova (Salzburg).

http://www.kurims.kyoto-u.ac.jp/~ichiro/