Extendable Partial Clones on a Finite Set
Boris A. Romov
By establishing the relational theory of extendable partial clones on a finite set we describe infinite descending chains of partial clones whose intersection cannot be determined by a finite set of relations (we call them not finitely definable). A special type of such chains introduced in case of clones by I.Rosenberg (1972) as a generalization of Post clones F∞4 and F∞8 is investigated. The criteria are established for the singular clones. A clone is called singular, if there is exactly one restriction-closed partial clone which has this clone as its total component. Based on that approach, applications to complexity of Constraint Satisfaction Problems are discussed.
Keywords: Galois connection, invariant relation, not finitely definable partial clone, extendable partial clone, singular clone, Constraint Satisfaction Problem.