School of Mathematical Sciences

Functional clones menu

Functional clones

Mark Jerrum (QMUL)
Mon, 25/03/2013 - 16:30
Seminar series: 

Relational clones (or co-clones) are sets of relations closed under "pp-definability": roughly speaking, conjunction and existential quantification. Over the 2-element domain they have been classified and form the well-known Post's lattice. I want here to consider "functional clones" of functions of arbitrary arities over a finite domain, closed under multiplication and summation over a subset of variables. What can be said about the lattice of functional clones? Even over the 2-element domain, the answer is probably too complex to describe sensibly, but some of the coarse structure can be uncovered.

In the course of the talk I'll be describing joint work with Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg and Colin McQuillan.

Speaker's webpage: