Geodesic
Tree transformations defined by hypersubstitutions
Discussiones Mathematicae. General Algebra and Applications, Tome 21 (2001) no. 2, pp. 219-227

Voir la notice de l'article provenant de la source Library of Science

Tree transducers are systems which transform trees into trees just as automata transform strings into strings. They produce transformations, i.e. sets consisting of pairs of trees where the first components are trees belonging to a first language and the second components belong to a second language. In this paper we consider hypersubstitutions, i.e. mappings which map operation symbols of the first language into terms of the second one and tree transformations defined by such hypersubstitutions. We prove that the set of all tree transformations which are defined by hypersubstitutions of a given type forms a monoid with respect to the composition of binary relations which is isomorphic to the monoid of all hypersubstitutions of this type. We characterize transitivity, reflexivity and symmetry of tree transformations by properties of the corresponding hypersubstitutions. The results will be applied to languages built up by individual variables and one operation symbol of arity n ≥ 2.
Keywords: hypersubstitution, tree transformation, tree transducer 
@article{DMGAA_2001_21_2_a6,
     author = {Arworn, Sr. and Denecke, Klaus},
     title = {Tree transformations defined by hypersubstitutions},
     journal = {Discussiones Mathematicae. General Algebra and Applications},
     pages = {219--227},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGAA_2001_21_2_a6/}
}
TY  - JOUR
AU  - Arworn, Sr.
AU  - Denecke, Klaus
TI  - Tree transformations defined by hypersubstitutions
JO  - Discussiones Mathematicae. General Algebra and Applications
PY  - 2001
SP  - 219
EP  - 227
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGAA_2001_21_2_a6/
LA  - en
ID  - DMGAA_2001_21_2_a6
ER  - 
%0 Journal Article
%A Arworn, Sr.
%A Denecke, Klaus
%T Tree transformations defined by hypersubstitutions
%J Discussiones Mathematicae. General Algebra and Applications
%D 2001
%P 219-227
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGAA_2001_21_2_a6/
%G en
%F DMGAA_2001_21_2_a6
Arworn, Sr.; Denecke, Klaus. Tree transformations defined by hypersubstitutions. Discussiones Mathematicae. General Algebra and Applications, Tome 21 (2001) no. 2, pp. 219-227. http://geodesic.mathdoc.fr/item/DMGAA_2001_21_2_a6/