tailieunhanh - Báo cáo khoa học: "SOME COMPUTATIONAL OF TREE ADJOINING"

Tree Adjoining G r a m m a r (TAG) is u formalism for natural language grammars. Some of the basic notions of T A G ' s were introduced in [Jo~hi,Levy, mad Takakashi I~'Sl and by [Jo~hi, l ~ l . A detailed investigation of the linguistic relevance of T A G ' s has been carried out in IKroch and Joshi,1985~. In this paper, we will describe some new results for TAG's, espe¢ially in the following areas: (I) parsing complexity of TAG's, (2) some closure results for TAG's, and (3) the relationship to Head grammars. . | SOME COMPUTATIONAL PROPERTIES OF TREE ADJOINING GRAMMARS K. Vijay-Shankir and Aravind K. Joshi Department of Computer and Information Science Room 288 Moore School D2 University of Pennsylvania Philadelphia PA 191C4 ABSTRACT Tree Adjoining Grammar TAG is a formalism for natural language grammars. Some of the basic notions of TAG S were introduced in Joshi Levy and Takahashi 197S and by Joshi 1983 . A detailed investigation of the linguistic relevance of TAG S has been carried out in Kroch and Joshi 1985 In this paper we will describe some new results for TAG S especially in the following areas 1 parsing complexity of TAG S 2 some closure results for TAG S and 3 the relationship to Head grammars. 2. TREE ADJOINING GRAMMARS TAG S We now introduce tree adjoining grammars TAG S . TAG S are more powerful than CFG s both weakly and TAG S were first introduced in Joshi Levy and Takahashi 1975 and Joshi 1983 . We include their description in this section to make the paper self-contained. We ean define a tree adjoining grammar as follows. A tree adjoining grammar G is a pair l A where I is a set of initial trees and A is a set of auxiliary trees. 1. INTRODUCTION A tree a is an initial tree if it is of the form a Investigation of constrained grammatical systems from the point of view of their linguistic adequacy and theừ computational tractability has been a major concern of computational linguists for the last several years. Generalized Phrase Structure grammars GPSG Lexical Functional grammars LFG Phrase Linking grammars PLG and Tree Adjoining grammars TAG are some key examples of grammatical systems that have been and still continue to be investigated along these lines. Some of the bask notions of TAG S were introduced in Joshi. Levy and Takahashi 1975 and Joshi 1983 . Some preliminary investigatione of the linguistk relevance and some computational properties were also carried out in Joshi 1983 . More recently a detailed investigation of the linguistic .