Compositions of Top-Down Tree Transducers with ε-Rules

摘要

Top-down tree transducers with e-rules (etdtts) 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 etdtts). A composition construction that composes two etdtts M and N is presented, and it is shown that the construction is correct, whenever (ⅰ) N is linear, (ⅱ) M is total or N is nondeleting, and (ⅲ) M has at most one output symbol in each rule.