Tensor envelopes of regular categories

We extend the calculus of relations to embed a regular category A into a family of pseudo-abelian tensor categories T(A,d) depending on a degree function d. Under the condition that all objects of A have only finitely many subobjects, our main results are as follows: 1. Let N be the maximal proper tensor ideal of T(A,d). We show that T(A,d)/N is semisimple provided that A is exact and Mal'cev. Thereby, we produce many new semisimple, hence abelian, tensor categories. 2. Using lattice theory, we give a simple numerical criterion for the vanishing of N. 3. We determine all degree functions for which T(A,d) is Tannakian. As a result, we are able to interpolate the representation categories of many series of profinite groups such as the symmetric groups S_n, the hyperoctahedral groups S_n\semidir Z_2^n, or the general linear groups GL(n,F_q) over a fixed finite field. This paper generalizes work of Deligne, who first constructed the interpolating category for the symmetric groups S_n. It also extends (and provides proofs for) a previous paper math.CT/0605126 on the special case of abelian categories.