Affiliations: Department of Foundations of Computer Science, University of Szeged, Árpád tér 2., H-6720 Szeged, Hungary. fulop@inf.u-szeged.hu | Institute for Natural Language Processing, Universität Stuttgart, Azenbergstr. 12, D-70174 Stuttgart, Germany. andreas.maletti@ims.uni-stuttgart.de | Faculty of Computer Science, Technische Universität Dresden, Mommsenstr. 13, D-01062 Dresden, Germany. heiko.vogler@tu-dresden.de
Note: [] Address for correspondence: Universität Stuttgart, Institute for Natural Language Processing, Azenbergstr. 12, D-70174 Stuttgart, Germany
Abstract: Weighted extended tree transducers (wxtts) over countably complete semirings are systematically explored. It is proved that the extension in the left-hand sides of a wxtt can be simulated by the inverse of a linear and nondeleting tree homomorphism. In addition, a characterization of the class of weighted tree transformations computable by bottom-up wxtts in terms of bimorphisms is provided. Backward and forward application to recognizable weighted tree languages are standard operations for wxtts. It is shown that the backward application of a linear wxtt preserves recognizability and that the domain of an arbitrary bottom-up wxtt is recognizable. Examples demonstrate that neither backward nor forward application of arbitrary wxtts preserves recognizability. Finally, a HASSE diagram relates most of the important subclasses of weighted tree transformations computable by wxtts.
Keywords: weighted tree transducer, preservation of recognizability, HASSE diagram, forward application, backward application
