Parsing Algorithms based on Tree Automata

Andreas Maletti and Giorgio Satta

11th International Conference on Parsing Technology (IWPT 2009)
Paris, France, 7th-9th October, 2009

---

Summary

We investigate several algorithms related to the parsing problem for weighted automata, under the assumption that the input is a string rather than a tree. This assumption is motivated by several natural 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 obtained by extending to weighted tree automata the Bar-Hillel technique, as defined for context-free grammars.

---

START Conference Manager (V2.56.8 - Rev. 780)