# FMCS'06 Abstracts

** Benno van den Berg: The free predicative topos **

The interplay between the free topos and the higher-order
intuitionistic type theory (HOTT) is well-established (see, e.g.,
"Introduction to higher order categorical logic" by Lambek and Scott).
This allows for purely categorical proofs to establish properties of
type theoretic systems: Freyd's purely categorical proof of the fact
that 1 is indecomposable projective in the free topos, for example,
shows the disjunction and existence property of HOTT.

Do similar methods work for predicative type theories, like
Martin-Löf type theory? To see that they do, one has to agree on a
notion of a "predicative topos". For this purpose I choose Moerdijk and
Palmgren's notion of a PiW-pretopos and I will show that the free
PiW-pretopos actually contains plenty of projective objects. Then I
will say something about its implications for type theory and the
comparison with the topos-theoretic case. [The contents are part of the
speaker's PhD thesis.]

** Eugenia Cheng: The periodic table of n-categories:
low-dimensional
results **

(Joint work with Nick Gurski.) We examine the periodic table of weak
n-categories for the low-dimensional cases. It is widely understood
that degenerate categories give rise to monoids, doubly degenerate
bicategories to commutative monoids, and degenerate bicategories to
monoidal categories; however, to understand the situation fully we
should examine the totalities of such structures. Categories naturally
form a 2-category **Cat** so we can take the full sub-2-category of
this whose 0-cells are the degenerate categories. On the other hand
monoids naturally form a category, but we can regard this as a discrete
2-category to make the comparison. We show that this construction does
not yield a biequivalence; to get an equivalence we must ignore the
natural transformations consider only the * category* of
degenerate categories.

A similar situation occurs for degenerate bicategories. The tricategory
of such does not yield an equivalence with monoidal categories; we must
consider only the categories of such structures.

For doubly degenerate bicategories the situation is more subtle. The
tricategory of such is not naturally triequivalent to the category of
commutative monoids (regarded as a tricategory). However in this case
considering just the categories does not give an equivalence either; to
get an equivalence we must consider the *bicategory* of doubly
degenerate bicategories.

We conclude with some remarks about how this situation might generalise
into higher dimensions.

** Peter Freyd: TBA **

Nicola Gambino: Pseudo-distributive laws: theory and
applications

Pseudo-distributive laws generalise ordinary distributive laws in order to describe
correctly the many examples in which different forms of algebraic structure on a
category interact by isomorphisms rather than equalities.

The purpose of this talk is to give a survey of the recent
research in the area, and
to describe some applications to logic and theoretical computer science. In particular, I
will show how pseudo-distributive laws play a fundamental role in the
construction of the cartesian closed bicategory of generalised species of
structures.

Brett Giles: Programming with
classical quantum datatypes

The aim of this talk is to describe a method of implementing quantum
programming languages based on a "quantum stack". The details of how
the stack architecture supports the implementation of datatypes (with
classical control) such as list and trees and transitions in the
quantum stack machine will be presented. A quantum programming
language, which compiles down to quantum stack operations, shall be
described. The language is based on Peter Selinger's Quantum
programming language. However, this language differs somewhat in that
it emphasizes the underlying "linear" semantics of the computations and
the role of

coproducts and datatypes. This makes it is more functional in
style (although, of course, it lacks higher order types).

** Wadii Hajji: Ehresmann semigroups from a range restriction
viewpoint **

** Robin Houston: Finite products are biproducts in a compact
closed
category **

If a compact closed category has finite products or finite coproducts,
then in fact has finite biproducts, and so is semi-additive (i.e.
enriched over
commutative monoids).

** André Joyal: Free bicompletion of categories (tutorial)
**

Free bicompletions of categories have applications to category theory,
theoretical computer science and game theory.
They are characterised by a special property called smothness.
The free bicompletion of a star autonomous category is star autonomous.
We shall describe the mathemetical tools needed for proving these
results.

** Tom Leinster: Operads (tutorial) **

This is an introduction to the theory and applications of
operads, with the emphasis on the theory.

In the first half I will give the basic definitions. Operads can
be viewed in two ways: (i) as algebraic theories; (ii) as
categorical structures in their own right. (Compare Lawvere
theories.) I will explain the two viewpoints and how they can be
useful in some diverse mathematical situations.

In the second half I will describe some generalizations of the
notion of operad useful in higher category theory. Again, such
generalized operads can be viewed in two ways: (i) as algebraic
theories of a rather sophisticated kind (including, for instance,
various theories of n-categories); (ii) as higher categorical
structures in their own right, of independent interest.

** Ernie Manes: Distributive laws and Kleisli strength (tutorial)
**

Some reminiscences about Jon Beck. Examples, basic and exotic.
Universal algebra in a symmetric monoidal category. The notion of
Kleisli strength (direct applications to distributive laws will be
discussed in a sequel talk given by Phil Mulry). Almost-closed
categories of algebras for monads in sets which may not be commutative.
Monad approximations (if time permits).

** Phil Mulry: Distributive laws and Kleisli strength **

In this talk we introduce and use the concept of Kleisli strength for
monads in an arbitrary symmetric monoidal category. These generalize
the
notion of commutative monads and there are new examples, even in the
cartesian-closed category of Sets. We exploit the presence of Kleisli
strength to derive methods for generating distributive laws, and
consequently monad compositions. We also describe mechanisms for
finding and generating new strengths, thus producing a large collection
of new
distributive laws.

** Jaap van Oosten: What is synthetic domain theory? (tutorial) **
(see slides here)

The tutorial aims to provide a first acquaintance
with the field of Synthetic Domain Theory. Rather than the usual
domain theory, which provides models for computation languages
by virtue of the way categories of domains are defined, SDT aims
to construct a theory where properties of certain categories of
sets (which then allow a similar modelling of computational
phenomena) follow axiomatically.
Synopsis of the tutorial:

- What is "synthetic"? As an example, we give a glimpse at Synthetic Differential Geometry
- What is Domain Theory? We quickly review some basic elements of the classical theory
- Why partial orders? A comment on meaning and use of posets
- The synthetic theory. The main part of the tutorial
- (If time permits) Models.
- Other "synthetic" developments.

** Thorsten Palm: Rudiments of a theory of polytopic sets **

The subject of * polytopes * has fascinated geometers ever
since
antiquity. It received a new direction about a quarter of a century
ago with the introduction of "abstract" polytopes. These structures
consist merely of faces and their incidences, independently of
realizations in (affine) space. A definition can be found in [1].

Almost all approaches to the subject of *higher-dimensional
categories* share a basic feature: the structures to be so named
are
underlain by collections of polytopes (of sorts) with common faces.
Such collections can be described formally as particular
*polytopic sets* with orientations. The notion of a polytopic
set
occured in [2] as a by-product of the definition of dendrotopic sets.
The accompanying polytopes are conceptually very similar to the
abstract ones of the geometers; their main difference is that two
faces are allowed to have many incidences.

In this talk I shall present miscellaneous items that may one day
constitute the core of a theory of polytopic sets.

[1] P. McMullen, E. Schulte: * Abstract Regular Polytopes *,
Cambridge University Press (2002)

[2] Thorsten Palm: `Dendrotopic Sets', in: * Galois Theory,
Hopf Algebras, and Semiabelian Categories* (= Fields Institute
Communications 43), AMS (2004), 393--443

** Craig Pastro: Quantum Categories **

(Joint work with Ross Street.) Quantum categories (and quantum
groupoids) were
introduced by Day and Street in order to find a common generalization
of Hopf
algebroids and groupoids. This talk will introduce a slightly
simplified
definition of quantum category and show how in Span(E) they become
categories
and in Comod(V) what people sometimes may call bialgebroids (or
bicoalgebroids).

** Dorette Pronk: More general spans **

Two years ago at FMCS I spoke about the universal properties of
the span construction for categories and hinted that one would be able
to
use these to define a span-construction for categories without
pullbacks
and even for 2-categories. What motivated us (Robert Dawson, Robert
Paré
and myself) to be interested in this, is that we wanted to understand
our Pi_2 construction for freely adding right adjoints as a
composition of a span construction and a path construction. I spoke
about the path construction at the October Fest last year, and it seems
appropriate to present the more general span construction at FMCS in
Kananaskis. We will see that oplax double categories (lax double
categories
would be the same as Leinster's fc-multi categories) play an essential
role
in the understanding of this construction for 2-categories. (As was the
case for the path construction.)

** Bob Rosebrugh: Constant complements, reversibility and
universal
view updates**

(Joint work with Michael Johnson.)
The concept of 'view' is an important element of data modelling. The
'view update problem': "when can a change in a view state be lifted to
a
total database state?" has been the subject of ongoing research in the
relational and other data models. The sketch data model (SkDM) provides
clear categorical criteria determining when there is an optimal (i.e.
universal) solution to this problem. We will review some of the
literature
on the view update problem and indicate how the SkDM solution relates
to
and extends this work.

** Philip Scott: Models of polarized multiplicative linear logic **

(Joint work with M. Hamano.)

** Alex Simpson: An abstract account of probability measures **

(joint work with Matthias Schroeder.)

shall discuss a universal property that characterizes an abstract space of all probability
measures over a given space. The
universal property supports the development of an associated theory of integration,
and allows easy proofs of fundamental
properties of integration. In the case of the category of topological spaces, the abstract space
of probability measures corresponds
to a standard construction (continuous probability
valuations with weak topology) and the abstract theory of integration coincides with
the usual concrete one.

** Paul Taylor: **

The talk will be a continuation of the talk given at the CMS meeting.

** Myles Tierney: Introduction to modern homotopy theory
(tutorial)**

I will give a short introduction to some methods of modern homotopy theory - modern
meaning since Quillen (1967). Thus, we will discuss weak factorization
systems, Quillen model categories (with a number of examples),
the homotopy category, left and right Quillen functors and Quillen
equivalences. A handout is here.

** Varmo Vene: Comonadic notions of computation **

(Joint work with Tarmo Uustalu) Slides are here.

We describe the semantics of a language with a general comonadic effect extending a pure
language (simply typed lambda calculus with products and optionally with
sums, recursion etc). Given a category modelling the pure language,
the translation reinterprets the constructs
of the pure language in the coKleisli category of a suitable (not necessarily
strong) symmetric monoidal comonad on the category. Clearly, the
coKleisli category does not necessarily have all the structure that the
base category does. It gets its finite products from the base
category, but the structure it has available for interpreting function or
sum types is generally weaker than that of categorical exponents or
coproducts. For example, the pseudo-exponents
are weak exponents (validate the beta-law), if the underlying symmetric monoidal
functor of the comonad respects the
comonoidal structure on the objects, and they are exponents, if
the comonad is strong
symmetric monoidal.

** Michael Warren: Homotopy models of intensional type theory **

We relate Quillen model categories and a form of intensional dependent
type
theory. In particular, we show how to interpret Martin-Löf's
identity
types in a model category.