Notions of Finiteness for Nominal Sets

Prelegent(ci)

Andrew Pitts

Afiliacja

University of Cambridge

Termin

11 października 2012 14:30

Pokój

p. 5820

Seminarium

Seminarium „Teoria automatów”

---

In the generalised version of nominal sets developed by the group in
Warsaw, the property of a structure having only finitely many orbits
plays a central role. I will discuss the relationship between
"orbit-finiteness" and other notions of finiteness that have been used
in connection with nominal sets---particularly order-theoretic ones.
This leads to a "full abstraction" result (joint work with Steffen
Loesch) for a symmetric version of the Ershov-Scott-Plotkin
extensional theory of computable functions of higher type, which I
will sketch. All this is with respect to the "equality symmetry"---the
version of nominal sets that I know best. The extent to which these
results extend to other data symmetries is open.

---