ON COMPUTATIONAL-COMPLEXITY OF CONTEXTUAL LANGUAGES

We consider the following restriction of internal contextual grammars, called local: in any derivation in a grammar, after applying a contex t, 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 t he latter type of grammars for natural. language study. In this aim, w e show that all the three basic non-context-free constructions in natu ral languages, that is, multiple agreements, crossed agreements, and d uplication, can be realized using this type of grammars. Our main resu lt is that these languages are parsable in polynomial time. The proble m of semilinearity remains open.