Paper: An Efficient Parsing Algorithm For Tree Adjoining Grammars

ACL ID P90-1036
Title An Efficient Parsing Algorithm For Tree Adjoining Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1990
Authors
  • Karin Harbusch (German Research Center for Artificial Intelligence, Saarbrucken Germany)

In the literature, Tree Adjoining Grammars (TAGs) are propagated to be adequate for nat- ural language description -- analysis as well as generation. In this paper we concentrate on the direction of analysis. Especially important for an implementation of that task is how efficiently this can be done, i.e., how readily the word problem can be solved for TAGs. Up to now, a parser with O(n 6) steps in the worst case was known where n is the length of the input string. In this paper, the result is improved to O(n 4 log n) as a new lowest upper bound. The paper demonstrates how local interpretion of TAG trees allows this reduction.