Power clones and non-deterministic hypersubstitutions

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, σ...

Full description

Saved in:
Bibliographic Details
Main Authors: K. Denecke, P. Glubudom, J. Koppitz
Format: Journal
Published: 2018
Subjects:
Online Access:https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77958520793&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/60554
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Chiang Mai University
id th-cmuir.6653943832-60554
record_format dspace
spelling th-cmuir.6653943832-605542018-09-10T03:45:05Z Power clones and non-deterministic hypersubstitutions K. Denecke P. Glubudom J. Koppitz Mathematics 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. 2018-09-10T03:45:05Z 2018-09-10T03:45:05Z 2008-06-01 Journal 17937183 17935571 2-s2.0-77958520793 10.1142/S1793557108000175 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77958520793&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/60554
institution Chiang Mai University
building Chiang Mai University Library
country Thailand
collection CMU Intellectual Repository
topic Mathematics
spellingShingle Mathematics
K. Denecke
P. Glubudom
J. Koppitz
Power clones and non-deterministic hypersubstitutions
description 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.
format Journal
author K. Denecke
P. Glubudom
J. Koppitz
author_facet K. Denecke
P. Glubudom
J. Koppitz
author_sort K. Denecke
title Power clones and non-deterministic hypersubstitutions
title_short Power clones and non-deterministic hypersubstitutions
title_full Power clones and non-deterministic hypersubstitutions
title_fullStr Power clones and non-deterministic hypersubstitutions
title_full_unstemmed Power clones and non-deterministic hypersubstitutions
title_sort power clones and non-deterministic hypersubstitutions
publishDate 2018
url https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77958520793&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/60554
_version_ 1681425457194467328