Tree transformations defined by hypersubstitutions

• Autorzy: Sr. Arworn , Klaus Denecke
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

hypersubstitution; tree transformation; tree transducer

Kategorie tematyczne

• 08B15: Lattices of varieties
• 08B25: Products, amalgamated products, and other kinds of limits and colimits

• Wydawca: Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra
• Czasopismo: Discussiones Mathematicae - General Algebra and Applications
• Rocznik: 2001
• Tom: 21
• Numer: 2
• Strony: 219-227

Daty

wydano

2001

otrzymano

2001-06-04

poprawiono

2001-11-30

Twórcy

autor

Sr. Arworn

• Chiang Mai University, Department of Mathematics, 50200 Chiang Mai, Thailand

autor

Klaus Denecke

• University of Potsdam, Institute of Mathematics, 14415 Potsdam, Germany

Bibliografia

• [1] K. Denecke, J. Koppitz and St. Niwczyk, Equational Theories generated by Hypersubstitutions of Type (n), Internat. J. Algebra Comput., to appear.
• [2] K. Denecke, D. Lau, R. Pöschel and D. Schweigert, Hyperidentities, Hyperequational classes and clone congruences, Contributions to General Algebra 7 (1991), 97-118.
• [3] K. Denecke and S.L. Wismath, The monoid of hypersubstitutions of type (2), Contributions to General Algebra 10 (1998), 109-126.
• [4] K. Denecke and S.L. Wismath, Hyperidentities and Clones, Gordon and Breach Sci. Publ., Amsterdam 2000.
• [5] F. Gécseg and M. Steinby, Tree Automata, Akadémiai Kiadó, Budapest 1984.
• [6] J.W. Thatcher, Tree Automata: an informal survey, 'Currents in the theory of computing', Prentice-Hall, Englewood Cliffs, NJ, 1973, 143-172.

Identyfikatory

DOI

10.7151/dmgaa.1039