Copenhagen Programming Language Seminar

Simulations, fibrations (joint work with R. Cockett).

Pieter Hofstra
University of Ottawa

Friday, June 6, 2008, 11:00-12:00
ITU, Rued Langgaards Vej 7, 2300 Copenhagen S. Room: Auditorium 3


In various situations in mathematics and computer science one wishes to consider mappings between structures which are not homomorphisms of any kind, but which capture the idea that one structure can interpret, or simulate, another structure. For example, an effective G"odel numbering of a structure A is a function from A to the natural numbers such that the relevant operations on A can be simulated by partial recursive functions. More generally, simulations between PCAs have proved useful in realizability and computability theory. In this talk I will describe a categorical theory of simulations in partial map categories and show how it captures some familiar examples. The theory is modular, in that several variations can be handled in the same framework. A key technical question is when a simulation is isomorphic to a functorial one, and the main technical result shows that simulation equivalences always may be presented as categorical equivalences.

Finally, we give a more conceptual picture of simulations by showing that they are in essence a Kleisli construction, namely for the (partitioned) assembly monad. The universal property of the construction will be explained in fibrational terms.

Scientific host: Lars Birkedal. Administrative host: Annette Enggaard. All are welcome.
The Copenhagen Programming Language Seminar (COPLAS) is a collaboration between DIKU, ITU, KVL and RUC.
COPLAS is sponsored by the FIRST Graduate School.
To receive information about COPLAS talks by email, send a message to prog-lang-request@mail.it-c.dk with the word 'subscribe' as subject or in the body.

For more information about COPLAS, see http://www.coplas.org