05771733

a

05771733 Maletti, Andreas Vogler, Heiko Compositions of top-down tree transducers with $\epsilon $-rules. Yli-Jyr\"a, Anssi (ed.) et al., Finite-state methods and natural language processing. 8th international workshop, FSMNLP 2009, Pretoria, South Africa, July 21--24, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-14683-1/pbk). Lecture Notes in Computer Science 6062. Lecture Notes in Artificial Intelligence, 69-80 (2010). 2010 Berlin: Springer EN

doi:10.1007/978-3-642-14684-8_8

Summary: Top-down tree transducers with $\epsilon $-rules ($\epsilon $tdtts) are a restricted version of extended top-down tree transducers. They are implemented in the framework Tiburon and fulfill some criteria desirable in a machine translation model. However, they compute a class of transformations that is not closed under composition (not even for linear and nondeleting $\epsilon $tdtts). A composition construction that composes two $\epsilon $tdtts $M$ and $N$ is presented, and it is shown that the construction is correct, whenever (i) $N$ is linear, (ii) $M$ is total or $N$ is nondeleting, and (iii) $M$ has at most one output symbol in each rule.