Abstract

Weighted tree transducers have been proposed as useful formal models for representing syntactic natural language processing applications, but there has been little description of inference algorithms for these automata beyond formal foundations. We give a detailed description of algorithms for application of cascades of weighted tree transducers to weighted tree acceptors, connecting formal theory with actual practice. Additionally, we present novel on-the-fly variants of these algorithms, and compare their performance on a syntax machine translation cascade based on (Yamada and Knight, 2001).

Date

2010

Authors

Jonathan May, Kevin Knight, Heiko Vogler

Conference

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics

Pages

1058-1066