Paper: Parsing Algorithms based on Tree Automata

ACL ID W09-3801
Title Parsing Algorithms based on Tree Automata
Venue International Conference on Parsing Technologies
Session Main Conference
Year 2009

We investigate several algorithms related to the parsing problem for weighted au- tomata, under the assumption that the in- put is a string rather than a tree. This assumption is motivated by several natu- ral language processing applications. We provide algorithms for the computation of parse-forests, best tree probability, inside probability (called partition function), and prefix probability. Our algorithms are ob- tained by extending to weighted tree au- tomata the Bar-Hillel technique, as defined for context-free grammars.