TAL Recognition in O(M(n2)) Time

TAL Recognition in O(M(n2)) Time Sanguthevar Rajasekaran Dept. of CISE, Univ. of Florida raj~cis.ufl.edu Shibu Yooseph Dept. of CIS, Univ. of Pennsylvania yooseph@gradient.cis.upenn.edu Abstract We propose an O(M(n2)) time algorithm for the recognition of Tree Adjoining Lan- guages (TALs), where n is the size of the input string and M(k) is the time needed to multiply two k x k boolean matrices. Tree Adjoining Grammars (TAGs) are for- malisms suitable for natural language pro- cessing and have received enormous atten- tion in the past among not only natural language processing researchers but also al- gorithms designers. The first polynomial time algorithm for TAL parsing was pro- posed in 1986 and had a run time of O(n6). Quite recently, an O(n 3 M(n)) algorithm has been proposed. The algorithm pre- sented in this paper improves the run time of the recent result using an entirely differ- ent approach. 1 Introduction The Tree Adjoining Grammar (TAG) formalism was introduced by :loshi, Levy and Takahashi (1975). TAGs are tree generating systems, and are strictly more powerful than context-free grammars. They belong to the class of mildly context sensitive gram- mars (:loshi, et al., 1991). They have been found to be good grammatical systems for natural lan- guages (Kroch, Joshi, 1985). The first polynomial time parsing algorithm for TALs was given by Vi- jayashanker and :loshi (1986), which had a run time of O(n6), for an input of size n. Their algorithm had a flavor similar to the Cocke-Younger-Kasami (CYK) algorithm for context-free grammars. An Earley-type parsing algorithm has been given by Schabes and Joshi (1988). An optimal linear time parallel parsing algorithm for TALs was given by Palls, Shende and Wei (1990). In a recent paper, Rajasekaran (1995) shows how TALs can be parsed in time O(n3M(n)). In this paper, we propose an O(M(n2)) time recognition algorithm for TALs, where M(k) is the time needed to multiply two k x k boolean matri- ces. The best known value for M(k) is O(n 2"3vs) (Coppersmith, Winograd, 1990). Though our algo- rithm is similar in flavor to those of Graham, Har- rison, & Ruzzo (1976), and Valiant (1975) (which were Mgorithms proposed for recognition of Con- text Pree Languages (CFLs)), there are crucial dif- ferences. As such, the techniques of (Graham, et al., 1976) and (Valiant, 1975) do not seem to extend to TALs (Satta, 1993). 2 Tree Adjoining Grammars A Tree Adjoining Grammar (TAG) consists of a quintuple (N, ~ U {~}, I, A, S), where N is a finite set of nonterminal symbols, is a finite set of terminal symbols disjoint from N, is the empty terminal string not in ~, I is a finite set of labelled initial trees, A is a finite set of auxiliary trees, S E N is the distinguished start symbol The trees in I U A are called elementary trees. All internal nodes of elementary trees are labelled with nonterminal symbols. Also, every initial tree is la- belled at the root by the start symbol S and …

Content truncated to 500 words