[Alta-Logic] Peripatetic talk

[Robin Cockett]

Apologies for the late announcement --- thanksgiving lethargy!

Time:  11:00am Wed. 12 Sept.

Place: ICT 616

Speaker:  Robin Cockett

Title: Timed Sets

A very simple construction is to associate with a (partial) function in 
sets a timing in some partially ordered commutative monoid:  two maps 
are then equal if, not only are they the same partial function, but also 
their timing is the same.   From the perspective of complexity one often 
wants to relax this very strict notion of equality to allow maps in the 
same "complexity class" to be equal.  For example, if we are considering 
P-time maps we may want two maps to be considered equal if, to within 
"polynomial bounds", their timings are equal.  

All this can be made good sense of categorically ...  what is a little 
surprising is that this, under certain very naturally conditions, makes 
timed sets into a restriction category -- in which the total maps are 
precisely those whose timing are
in the complexity class one started with.  This allows one to construct 
categories which not only directly express complexity but also express 
computability (in the sense of being Turing categories) while having 
their total maps belonging to a low complexity classes.

Joint work with Ximo Boils, Jonathan Gallagher, and Pavel Hubres