Header menu link for other important links
X
Internal contextual grammars for mildly context-sensitive languages
Raghavan Rama, , Krishna S.N, Martin-Vide C.
Published in
2007
Volume: 5
   
Issue: 2
Pages: 181 - 197
Abstract
Contextual grammars were introduced by Marcus (Revue Roumaine de Mathematiques Pures et Appliquees 14:525-1534, 1969) based on the basic phenomenon in descriptive linguistics, that of acceptance of a word by a context or conversely. In this paper we present some results which are of interest for the potential application of contextual grammars to natural languages. We introduce some classes of internal contextual grammars, viz. maximum depth-first grammars, maximum lengthwise depth-first grammars, and absorbing right context grammars. The study of these classes is motivated by their potential linguistic relevance for natural languages. In particular, we analyze these variants with respect to the properties of mildly context-sensitive languages. With this aim, we first show that the three basic non-context-free constructions in natural languages can be realized upon using all such variants. Secondly, we state that the membership problem for the family of absorbing right context contextual languages is decidable by a polynomial time algorithm. Finally, we show that absorbing right context grammars produce semilinear languages only. Besides, we show that the non-marked duplication language can be generated by absorbing right context grammars, which is a unique feature not present in any other variant of contextual grammars. © 2007 Springer Science+Business Media B.V.
About the journal
JournalResearch on Language and Computation
ISSN15707075
Open AccessNo