Unique inclusions of maximal C-clones in maximal clones

Abstract

$C$-clones are polymorphism sets of so-called clausal relations, a special type of relations on a finite domain, which first appeared in connection with constraint satisfaction problems in [Creignou et al. 2008]. We completely describe the relationship w.r.t. set inclusion between maximal $C$-clones and maximal clones. As a main result we obtain that for every maximal $C$-clone there exists exactly one maximal clone in which it is contained. A precise description of this unique maximal clone, as well as a corresponding completeness criterion for $C$-clones is given.

arXiv comment20 pages

Cited by in corpus (1)

• The number of clones determined by disjunctions of unary relations