Narrow Results

We prove that there are continuum many clones on a three-element set even if they are considered up to homomorphic equivalence. The clones we use to prove this fact are clones consisting of self-dual operations, i.e. operations that preserve the relation $\{(0,1),(1,2),(2,0)\}$. However, there are only countably many such clones when considered up to equivalence with respect to minor-preserving maps instead of clone homomorphisms. We give a full description of the set of clones of self-dual operations, ordered by the existence of minor-preserving maps. Our result can also be phrased as a statement about structures on a three-element set: we give a full description of the structures containing the relation $\{(0,1),(1,2),(2,0)\}$, ordered by primitive positive constructability, because there is a minor-preserving map from the polymorphism clone of a finite structure $𝔄$ to the polymorphism clone of a finite structure $𝔅$ if and only if there is a primitive positive construction of $𝔅$ in $𝔄$.

An important measure of clone detection performance is precision. However, there has been a marked lack of research into methods for efficiently and accurately measuring the precision of a clone detection tool. Instead, tool authors simply validate a small random sample of the clones their tools detected in a subject software system. Since there could be many thousands of clones reported by the tool, such a small random sample cannot guarantee an accurate and generalized measure of the tool’s precision for all the varieties of clones that can occur in any arbitrary software system. In this paper, we propose a machine-learning-based approach that can cluster similar clones together, and which can be used to maximize the variety of clones examined when measuring precision, while significantly reducing the biases a specific subject system has on the generality of the precision measured. Our technique reduces the efforts in measuring precision, while doubling the variety of clones validated and reducing biases that harm the generality of the measure by up to an order of magnitude. Our case study with the NiCad clone detector and the Java class library shows that our approach is effective in efficiently measuring an accurate and generalized precision of a subject clone detection tool.

Hypersubstitutions map operation symbols to terms of the corresponding arity. Any hypersubstitution can be extended to a mapping defined on the set W_τ(X) of all terms of type τ. If σ : {f_i | i ∈ I} → W_τ(X) is a hypersubstitution and its canonical extension, then the set

A set $C$ of operations defined on a nonempty set $A$ is said to be a clone if $C$ is closed under composition of operations and contains all projection mappings. The concept of a clone belongs to the algebraic main concepts and has important applications in Computer Science. A clone can also be regarded as a many-sorted algebra where the sorts are the $n$-ary operations defined on set $A$ for all natural numbers $n\ge 1$ and the operations are the so-called superposition operations $S_m^n$ for natural numbers $m,n\ge 1$ and the projection operations as nullary operations. Clones generalize monoids of transformations defined on set $A$ and satisfy three clone axioms. The most important axiom is the superassociative law, a generalization of the associative law. If the superposition operations are partial, i.e. not everywhere defined, instead of the many-sorted clone algebra, one obtains partial many-sorted algebras, the partial clones. Linear terms, linear tree languages or linear formulas form partial clones. In this paper, we give a survey on partial clones and their properties.

A classical theorem of Baker and Pixley states that if $A$ is a finite algebra with a majority term and $f$ is an $n$-ary operation on $A$ which preserves every subuniverse of $A\times A$, then $f$ is representable by a term in $A$. We give a generalizacion of this theorem for the case in which $A$ is a finite algebra belonging to some relatively congruence distributive quasivariety.