A formal approach to subgrammar extraction for NLP

✍ Scribed by Vlado Kešelj; Nick Cercone

• Book ID: 104046030
• Publisher: Elsevier Science
• Year: 2007
• Tongue: English
• Weight: 223 KB
• Volume: 45
• Category: Article
• ISSN: 0895-7177
• DOI: 10.1016/j.mcm.2006.06.001

✦ Synopsis

The problem of subgrammar extraction is precisely defined in the following way: Given a grammar G and a set of words W , find a smallest subgrammar of G that accepts the same set of sentences from W * as G, and for each of them produces the same parse trees. In practical Natural Language Processing applications, the set of words W is obtained from the text unit. There are practical motivations for doing this operation "just-in-time", i.e. just before processing the text; hence it is required that this operation be done in an automatic and efficient way. After defining the problem in the general framework, we discuss the problem for context-free grammars (CFG), and give an efficient algorithm for it. We prove that finding the smallest subgrammar for HPSGs is an NP-hard problem, and give an efficient algorithm that solves an easier, approximate version of the problem. We also discuss how the algorithm can be efficiently implemented.