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:

  1. What is "synthetic"? As an example, we give a glimpse at Synthetic Differential Geometry
  2. What is Domain Theory? We quickly review some basic elements of the classical theory
  3. Why partial orders? A comment on meaning and use of posets
  4. The synthetic theory. The main part of the tutorial
  5. (If time permits) Models.
  6. 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.