Category Theory and Computer Science (CTCS'04)
August 12th-14th, 2004
Appsem II conference

Invited Talks

Speaker: Andrew Pitts
Title:Nominal Semantics of Abstraction and Restriction

Many uses of names in programming languages and logical calculi are "atomic", in the sense that the structure of a name is immaterial: all that matters are distinctions between names and the association of names to the things named. In this talk I will give a gentle introduction to the topos of "nominal sets", a mathematical framework with names as atoms that can express the crucial property of "freshness" of names in a syntax-independent way. There are simple constructions on nominal sets for exponentiation, for name-abstraction and for name-restriction that illuminate the relationship between these notions and that of dynamic allocation of names in operational semantics. The category-theoretic characterisation and properties of name-abstraction and name-restriction hint at a categorical algebra for "equations modulo freshness constraints" that has yet to be investigated.

Speaker: Robin Milner
Title:Categorical aspects of bigraphs

I shall discuss how Jamey Leifer, Ole Hoegh Jensen and I have set up the mathematical model of bigraphs, and where categorical ideas are useful. Bigraphs represent the dynamics of reconfigurable systems; their nodes can be nested and their edges don't have to respect the nesting (hence "bi"). They generalise process calculi (pi calculus, ambients, ...), and they can also model concrete "informatic" systems like people walking in and out of buildings carrying hand-held devices, plugging them into computers, and being detected (with benevolent intent) by sensors.
For modelling process calculi, including transition systems and bisimilarity, relative pushouts (RPOs) have provided a uniform basis. This is set up using s-categories, a well-behaved kind of precategory which allows one to keep track of the identity of graphical entities. Within this frame we recover already-known behavioural theories of processes.
Sorting is used to ensure that we get surjective (no junk) translations of processes. The forgetful functor that discards sorts must create RPOs if we are to use the behavioural theory; there are nice sufficient conditions for a functor to have this property, and these condtiions are satisfied by very useful sorting disciplines, including one that represents binding and scoping on names.
The aim of the talk is to expose these ideas to category theorists and receive comments and criticism in exchange.

Speaker: Martin Hyland
Title:Categrical construction of innocence

The notion of innocent strategy as currently understood was one component in a games model for PCF, and has become an established part of game semantics. However the noton has seemed ad hoc to many and honest proofs of its properties can seem fiddly. In this work we describe a categorical context allowing a rational reconstruction of innocent and other similar strategies.

Speaker:Thomas Streicher
Title:A Universal Model for the Infinitary CPS Language via Laird Domains

About 2 years ago Jim Laird has introduced a new kind of domains providing a fully abstract model for SPCF (i.e. PCF + catch) with non-recuperable errors. One can show that Laird domains provide a universal model for infinitary SPCF (i.e. with infinite terms). This has already been shown by J.Laird. But we give a simpler proof of this fact by showing that already type 1 over the natural numbers is universal for Laird domains. SPCF hosts the recursive type $D \cong [D^\omega \to \Sigma]$ which provides a model for infinitary CPS target language (sort of an infinitary lambda-calculus). It can be shown that every term of SPCF can be ``realized'' by an object of D that can be denoted by a term of the infinitary CPS language. From this it follows that every object of D appears as denotation of an appropriate term of infinitary CPS, i.e. that D is a universal model. However, the model is not ``fully complete'' because different infinite normal forms receive the same interpretation in D. This suggests that $\lambda$ -calculus is not the optimal representation of sequential algorithms or, rather, that the model D might give rise to an optimizing translation. This is joint work with my student Tobias Löw.

Speaker:François Bergeron
Title:Species and Variations on the Theme of Species

We will present, for non combinatorialists, the basic combinatorial motivations behind the development of the notion of Species of Structures and show why one should also consider variants of the notion. This will lead to consider Hopf algebra like structures on categories. we will illustrate with many examples.