From Contextual Grammars to Range Concatenation Grammars

✍ Scribed by Pierre Boullier

• Book ID: 104445825
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 818 KB
• Volume: 53
• Category: Article
• ISSN: 1571-0661
• DOI: 10.1016/s1571-0661(05)82573-3

✦ Synopsis

Though the eld of natural language processing is one of the major aims that has led to the de nition of contextual grammars, very little was made on that subject. One reason is certainly the lack of e cient parsers for contextual languages. In this paper we s h o w h o w some subclasses of contextual grammars can be translated into equivalent range concatenation grammars and can thus be parsed in polynomial time. However, on some other subclasses, this translation schema only succeeds if the range concatenation grammar formalism is extended. We show that the languages de ned by s u c h an extension may need an exponential parse time.