Michael Kompatscher

Polynomial Definability in Constraint Languages with Few Subpowers

Abstract. A first-order formula is called primitive positive (pp) if it uses only existential quantifiers and conjunctions. Primitive positive formulas are a central concept in (fixed-template) constraint satisfaction, as [Formula: see text] can be viewed as the problem of decidi...

Mal'cev clones over a three-element set up to minor-equivalence

We classify all Mal'cev clones over a three-element set up to minion homomorphisms. This is another step toward the complete classification of three-element relational structures up to pp-constructability. We furthermore provide an alternative proof of Bulatov's result that all M...