Torsten Stüber

"Decomposition of Weighted Multioperator Tree Automata"

Abstract:
In [Eng75] Joost Engelfriet proved the decomposition of the class BOT of
bottom-up tree transformations into the classes REL, FTA and HOM of
relabeling tree transformations, finite-state tree automata and
homomorphism tree transformations, respectively (i.e., BOT=REL;FTA;HOM).
In [Mal04] A. Maletti revived a definition of weighted bottom-up tree
automata, in which the weight algebra is not a semiring but a
multioperator monoid (cf. [Kui98]). Maletti proved that bottom-up tree
transducers can be simulated by such weighted automata.
In my talk I will show how Engelfriet's decomposition result can be
generalized to weighted multioperator tree automata.

References:
[Eng75] J. Engelfriet. Bottom-up and top-down tree transformations - a
comparison. Math. Systems Theory, 9(3):198-231, 1975
[Mal04] A. Maletti. Relating tree series transducers and weighted tree
automata. In C.S. Calude, editor, DLT'04 - 8th International Conference on
Delevopments in Language Theory, Auckland, New Tealand, December 13-17,
2004, volume 3340 of LNCS, paged 321-333, 2004.
[Kui98] W. Kuich. Formal power seried over trees. In S. Bozapalidis,
editor, 3rd International Conference on Developments in Language Theory,
DLT 1997, Thessaloniki, Greece, Proceedings, pages 61-101. Aristotle
University of Thessaloniki, 1998.