An Efficient Parsing Algorithm for Tree Adjoining Grammars

AN EFFICIENT PARSING ALGORITHM FOR TREE ADJOINING GRAMMARS Karin Harbusch DFKI - Deutsches Forschungszentrum fiir Kfinstliche Intelligenz Stuhlsatzenhausweg 3, D-6600 Saarbriicken 11, F.R.G. harbusch~dfki.uni-sb.de ABSTRACT 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. 1 INTRODUCTION Compared with the formalism of context-free grammars ( CFC, s), the rules of Tree Adjoining Grammars (TAGs) can be imagined intuitively as parts of context-free derivation trees. Without paying attention to the fact that there are some more restrictions for these rules, the recursion op- eration (adjoining) is represented as replacing a node in a TAG rule by another TAG rule so that larger derivation trees are built. This close relation between CFGs and TAGs can imply that they are equivalent. But TAGs are more powerful than context-free grammars. This additional power -- characterized as mildly context-sensitive -- leads to the question of whether there are efficient algorithms to solve the word problem for TAGs. Up to now, the algorithm of Vijay-Shanker and Joshi with a time complexity of O(n 6) for the worst case was known, in addition to several un- successful attempts to improve this result. This paper's main emphasis is on the improvement of this result. An efficient parser for Tree Adjoining Grammars with a worst case time complexity of O(n 4 log n) is discussed. All known parsing algorithms for TAGs use the close structural similarity between TAGs and CFGs, which can be expressed by writing all inner nodes and all their sons in a TAG as the rule set of a context-free grammar (the context-free ker- nelof a TAG). Additionally, the constraint has to be tested that all further context-free rules corre- sponding to the same TAG tree must appear in the derivation tree, iff one rule of that TAG tree is in use. Therefore, it is clear that a context-free parser can be the basis for extensions representing the test of the additional constraint. On the basis of the two fundamental context- free analysers, the different approaches for TAGs 284 can be divided into two classes. One class extends an Earley parser and the second class extends a Cocke-Kasami- Younger ( CKY) parser for CFGs. Here, we focus on the approaches with a CKY basis, because the relation between the resulting triangle matrix and the encoded derivation trees is closer than for the item lists of an Earley parser. In particular, the paper is …

Content truncated to 500 words