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 σ : {f i | i ∈ I} → W τ (X) is a hypersubstitution and [Formula: see text] its canonical extension, then the set [Formula: see text] 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 [Formula: see text]. Since the set of all hypersubstitutions of type r forms a semigroup with respect to the multiplication [Formula: see text], 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 [Formula: see text] be the power set of the set of all n-ary terms of type τ. Then we define a superposition operation [Formula: see text] and get a heterogeneous algebra [Formula: see text] (ℕ + is the set of all positive natural numbers), which is called the power clone of type τ. We prove that the algebra [Formula: see text] 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 [Formula: see text] 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 [Formula: see text] are 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.