Search

The critical relations are the building blocks of the relational clone of a relational structure with respect to the relational operations intersection and direct product. In this paper we describe the critical relations of crowns. As a consequence, we obtain that the subpower membership problem for any crown is polynomial-time solvable.

In the first part of this paper we present a new family of finite bounded posets whose clones of monotone operations are not finitely generated. The proofs of these results are analogues of those in the famous paper of Tardos. Another interesting family of finite posets from the finite generability point of view is the family of locked crowns. To decide whether the clone of a locked crown where the crown is of at least six elements is finitely generated or not one needs to go beyond the scope of Tardos’s proof. Although our investigations are not conclusive in this direction, they led to the results in the second part of the paper. We call a monotone operation ascending if it is greater than or equal to some projection. We prove that the clones of bounded posets are generated by certain ascending idempotent monotone operations and the 0 and 1 constant operations. A consequence of this result is that if the clone of ascending idempotent operations of a finite bounded poset is finitely generated, then its clone is finitely generated as well. We provide an example of a half bounded finite poset whose clone of ascending idempotent operations is finitely generated but whose clone is not finitely generated. Another interesting consequence of our result is that if the clone of a finite bounded poset is finitely generated, then it has a three element generating set that consists of an ascending idempotent monotone operation and the 0 and 1 constant operations.

The \({\mathcal C}\)-subfunction relations on the set of operations on a finite base set \(A\) defined by function classes \({\mathcal C}\) are examined. For certain clones \({\mathcal C}\) on \(A\), it is determined whether the partial orders induced by the respective \({\mathcal C}\)-subfunction relations have infinite descending chains or infinite antichains. More specifically, we investigate the subfunction relations defined by the clone of all functions on \(A\), the clones of essentially at most unary operations, the clones of linear functions on a finite field, and the clones of monotone functions with respect to the various partial orders on \(A\).

In 1986 Tardos proved that for the poset 1+2+2+2+1, the clone of monotone operations is nonfinitely generated. We generalize his result in the class of series parallel posets. We characterize the posets with nonfinitely generated clones in this class by the property that they have a retract of the form either 1+2+2+2+1, 2+2+1, or 1+2+2.

There is only one maximal clone on a set of at most eight elements which has not been known to be finitely generated. We show that it is not finitely generated.

Let R8 denote the 8-element bounded tower. G. Tardos has shown that C(R8), the clone of all monotone functions on R8, is not finitely generated. In this paper we show that the clone of all nonsurjective functions is finitely generated.