Narrow Results

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.

We show that if G ≤ S_A is a permutation group on a finite set A satisfying |A| ≥ 3, then the set of G-closed clones on A that contain all constant operations is finite iff G = S_A, A_A, AGL(1,5) (|A| = 5), PSL(2,5) (|A| = 6), PGL(2,5) (|A| = 6), PGL(2,7) (|A| = 8), PGL(2,8) (|A| = 9), or PΓL(2,8) (|A| = 9).

In 1999, Bergman et al. showed that the following two problems are EXPTIME-complete: GENCLO, which decides whether an operation on a finite set A belongs to a clone generated by a finite set of operations on A; and TERMEQUIV, which decides whether two algebras on the same finite set and with finitely many fundamental operations are term-equivalent. However, the proof of one of the key statements was not correct. Using the techniques proposed by Bergman et al., in this paper we present the correct proof.

Algebras on the natural numbers and their clones of term operations can be classified according to their descriptive complexity. We give an example of a closed algebra which has only unary operations and whose clone of term operations is not Borel. Moreover, we provide an example of a coatom in the clone lattice whose obvious definition via an ideal of subsets of natural numbers would suggest that it is complete coanalytic, but which turns out to be a rather simple Borel set.

A finite unary algebra of finite type with a constant function 0 that is a one-element subalgebra, and whose operations have range {0, 1}, is called a {0, 1}-valued unary algebra with 0. Such an algebra has a finite basis for its quasi-equations if and only if the relation defined by the rows of the nontrivial functions in the clone form an order ideal.

For $n$ a positive integer and $K$ a finite set of finite algebras, let $L(n,K)$ denote the largest $n$-generated subdirect product whose subdirect factors are algebras in $K$. When $K$ is the set of all $n$-generated subdirectly irreducible algebras in a locally finite variety ${𝒱}$, then $L(n,K)$ is the free algebra $F_{{𝒱}}(n)$ on $n$ free generators for ${𝒱}$. For a finite algebra $A$ the algebra $L(n,\{A\})$ is the largest $n$-generated subdirect power of $A$. For every $n$ and finite $A$ we provide an upper bound on the cardinality of $L(n,\{A\})$. This upper bound depends only on $n$ and these basic parameters: the cardinality of the automorphism group of $A$, the cardinalities of the subalgebras of $A$, and the cardinalities of the equivalence classes of certain equivalence relations arising from congruence relations of $A$. Using this upper bound on $n$-generated subdirect powers of $A$, as $A$ ranges over the $n$-generated subdirectly irreducible algebras in ${𝒱}$, we obtain an upper bound on $|F_{{𝒱}}(n)|$. And if all the $n$-generated subdirectly irreducible algebras in ${𝒱}$ have congruence lattices that are chains, then we characterize in several ways those ${𝒱}$ for which this upper bound is obtained.

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.

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 $𝔄$.

Two algebraic structures with the same universe are called term-equivalent if they have the same clone of term operations. We show that the problem of determining whether two finite algebras of finite similarity type are term-equivalent is complete for deterministic exponential time.

China seeks to develop biofuels industry despite production difficulties.

Shengquan and Novozymes team up to commercialize cellulosic ethanol.

China, Denmark establish first national renewable energy think tank.

Bayer HealthCare, Tsinghua University extend innovative drug discovery partnership.

CUHK launches non-invasive prenatal test for Down Syndrome.

World's 1st handmade cloned transgenic sheep born in China.

American genetics helps meet Chinese demands for more protein.

China's colorectal cancer drug market expected to grow to more than $400 million in 2016.

Medistem appoints director of Chinese operations.

In this paper, among other results, we prove that a clone C with five essentially binary operations is minimal if and only if C is a clone of a non-trivial affine space over GF(7). This result is a product of systematic investigation of varieties of idempotent commutative groupoids. It is probably the most spectacular result of this investigation, but many other results formulated and proved throughout the paper may turn out more useful in further study in this area.

P-Compatibility is a hereditary property of identities which generalizes the properties of normality and externality of identities. Chajda characterized the normalization of a variety by an algebraic construction called a choice algebra. In this paper, we generalize this characterization to the least P-compatible variety P(V) determined by a variety V for any partition P using P-choice algebras. We also study the clone of (strongly) P-compatible n-ary terms of a variety V, and relate identities of this clone to (strongly) P-compatible hyperidentities of the variety V.

The superposition of cooperations satisfies the well-known clone axioms (C1), (C2) and (C3). We define terms for indexed coalgebras of type τ, cooperations induced by those terms, and prove that the set of all induced cooperations forms a clone. This clone is equal to the clone of all cooperations generated by the fundamental cooperations of an indexed coalgebra. Finally, we introduce the concept of rational equivalence for coalgebras and determine all two-element coalgebras up to rational equivalence.

A clone is a set of operations defined on a base set A which is closed under composition and contains all the projection operations. There are several ways to regard a clone as an algebraic structure (see e.g. [3]). If f, g₁,…,g_n : Aⁿ → A are n-ary operations defined on A, then by Sⁿ(f, g₁ … , g_n)(a₁ … , a_n) := f(g₁(a₁,…,a_n),…,g_n(a₁,…,a_n)) for all a₁,…, a_n ∈ A an (n + 1)-ary operation on the set Oⁿ(A) of all n-ary operations can be defined. From this operation one can derive a binary operation + defined by f + g := Sⁿ(f, g,…,g) and obtains a semigroup (Oⁿ(A);+). The collection of all clones of operations on a finite set forms a complete lattice. This lattice is well-described ([4], [5]) if |A| = 2. If |A| > 2, this lattice is uncountably infinite and very complex. In this paper instead of clones we study semigroups of n-ary operations, i.e. subsemigroups of the semigroup (Oⁿ(A); +) and their properties. We look for idempotent and regular elements of (Oⁿ(A); +), consider Green's relations for the semigroup (Oⁿ(A); +), characterize all constant subsemigroups of (Oⁿ(A);+), all semilattices, rectangular bands and normal bands contained in (Oⁿ(A);+).

A clone is a set of operations defined on a base set A which is closed under composition and contains all the projection operations. There are several ways to regard a clone as an algebraic structure (see e.g. [3]). If f, g₁, … , g_n : Aⁿ → A are n-ary operations defined on A, then by

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 term which is a formal expression defined by variables and operation symbols can be described by tree diagram. The class of terms under which the longest distance from the root to each vertex is equal is called completely expanded. In this paper, we consider the partial many-sorted operation defined on the family of all completely expanded terms of type $\tau$ and construct the partial algebra satisfying the clone axioms. The partial operations on arbitrary algebra generated by completely expanded terms and their related structures are obtained.

Hypersubstitutions map operation symbols to terms of the corresponding arities. Using hypersubstitutions from each algebra one can derive new algebras. We compare properties of congruence lattices, of subalgebra lattices and of clones of the derived algebras with the corresponding properties of the starting algebras. If both algebras have the same clone of term operations, then they have the most properties in common. This is for instance the case if the hypersubstitution is surjective. We characterize surjective hypersubstitutions and prove that for finite types surjective hypersubstitutions are bijective. This will be applied to i-closed varieties of n-ary type.