Publication at Faculty of Mathematics and Physics |
2010
Abstract
Each clone C on a fixed base set A induces a quasi-order on the set of all operations on A by the following rule f is a e-minor of g if f can be obtained by substituting operations from e for the variables of g. By making use of a representation of Boolean functions by hypergraphs and hypergraph homomorphisms, it is shown that a clone C on {0, 1} has the property that the corresponding C-minor partial order is universal if and only if C is one of the countably many clones of clique functions or the clone of self-dual monotone functions.
Furthermore, the C.-minor partial orders are dense when C is a clone of clique functions.