Power clones and non-deterministic hypersubstitutions

Abstract

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 σ : {fi| i ∈ I} → Wτ(X) is a hypersubstitution and σ̄ : Wτ(X) → Wτ(X) its canonical extension, then the set Tσ:= {(t, σ̄[t])|t∈Wτ(X)} is a tree transformation where the original language and the image language are of the same type. Tree transformations of the type Tσcan be produced by tree transducers. Here Tσis the graph of the function σ̄. Since the set of all hypersubstitutions of type r forms a semigroup with respect to the multiplication σ1ohσ2:= σ1o σ2, semigroup properties influence the properties of tree transformations of the form Tσ. For instance, if σ is idempotent, the relation Tσis transitive (see [1]). Non-deterministic tree transducers produce tree transformations which are not graphs of some functions. If such tree transformations have the form Tσ, then σ is no longer a function. Therefore, there is some interest to study non-deterministic hypersubstitutions. That means, there are operation symbols which have not only one term of the corresponding arity as image, but a set of such terms. To define the extensions of non-deterministic hypersubstitutions, we have to extent the superposition operations for terms to a superposition defined on sets of terms. Let P(Wτ(Xn)) be the power set of the set of all n-ary terms of type τ. Then we define a superposition operation Ŝnm: P(Wτ(Xn)) × (P(Wτ(Xm)))n→ P(Wτ(Xm)) and get a heterogeneous algebra P cloneτ := (P(Wτ(Xn)))n∈ℕ+; Ŝnmm,n∈ℕ+, ({xi}i≤n,n∈ℕ+), (ℕ+is the set of all positive natural numbers), which is called the power clone of type τ. We prove that the algebra P cloneτ satisfies the well-known clone axioms (C1), (C2), (C3), where (C1) is the superassociative law (see e.g. [5], [4]). It turns out that the extensions of non-deterministic hypersubstitutions are precisely those endomorphisms of the heterogeneous algebra P cloneτ which preserve unions of families of sets. As a consequence, to study tree transformations of the form Tσ, where σ is a non-deterministic hypersubstitution, one can use the structural properties of non-deterministic hypersubstitutions. Sets of terms of type τ are tree languages in the sense of [3] and the operations Ŝnmare operations on tree languages. In [3] also another kind of superposition of tree languages is introduced which generalizes the usual complex product of subsets of the universe of a semigroup. We show that the extensions of non-deterministic hypersubstitutions are not endomorphisms with respect to this kind of superposition. © 2008 World Scientific Publishing Company.