Paper: Some Computational Properties Of Tree Adjoining Grammers

ACL ID P85-1011
Title Some Computational Properties Of Tree Adjoining Grammers
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1985
Authors

Tree Adjoining Grammar (TAG) is u formalism for natural language grammars. Some of the basic notions of TAG'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 TAG'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.