Equivalence of operations with respect to discriminator clones

Abstract

For each clone C on a set A there is an associated equivalence relation, called C-equivalence, on the set of all operations on A, which relates two operations iff each one is a substitution instance of the other using operations from C. In this paper we prove that if C is a discriminator clone on a finite set, then there are only finitely many C-equivalence classes. Moreover, we show that the smallest discriminator clone is minimal with respect to this finiteness property. For discriminator clones of Boolean functions we explicitly describe the associated equivalence relations.

17 pages

References in corpus (1)

• Subfunction relations defined by the clones containing all unary operations

Cited by in corpus (7)

• Generalizations of Swierczkowski's lemma and the arity gap of finite functions
• Decompositions of functions based on arity gap
• The arity gap of order-preserving functions and extensions of pseudo-Boolean functions
• Clones with finitely many relative R-classes
• The arity gap of polynomial functions over bounded distributive lattices
• Clonoids of Boolean functions with essentially unary, linear, semilattice, or 0- or 1-separating source and target clones
• Clonoids of Boolean functions with a monotone or discriminator source clone