On computational complexity of contextual languages

✍ Scribed by Lucian Ilie

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 726 KB
• Volume: 183
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00309-x

✦ Synopsis

We consider the following restriction of internal contextual grammars, called local: in any derivation in a grammar, after applying a context, further contexts can be added only inside of or at most adjacent to the previous ones. We further consider a natural restriction of this derivation mode by requiring that no superword of the word considered as selector can be used as selector. We investigate the relevance of the latter type of grammars for natural language study. In this aim, we show that all the three basic non-context-free constructions in natural languages, that is, multiple agreements, crossed agreements, and duplication, can be realized using this type of grammars. Our main result is that these languages are parsable in polynomial time. The problem of semilinearity remains open.