Header menu link for other important links
X
On the relative expressive power of contextual grammars with maximal and depth-first derivations
Kamala Krithivasan
Published in
2009
Volume: 5684 LNCS
   
Pages: 246 - 260
Abstract
In the recent years, several new classes of contextual grammars have been introduced to give an appropriate model description to natural languages. With this aim, some new families of contextual languages have been introduced based on maximal and depth-first conditions and analyzed in the framework of so-called mildly context sensitive languages. However, the relationship among these families of languages have not yet been analyzed in detail. In this paper, we investigate the relationship between the families of languages whose grammars are based on maximal and depth-first conditions. We prove an interesting result that all these families of languages are incomparable to each other, but they are not disjoint. © 2009 Springer Berlin Heidelberg.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN03029743
Open AccessNo
Concepts (13)
  •  related image
    Appropriate models
  •  related image
    Contextual grammars
  •  related image
    DEPTH-FIRST
  •  related image
    Expressive power
  •  related image
    INCOMPARABLE
  •  related image
    INTERNAL CONTEXTUAL GRAMMARS
  •  related image
    MAXIMAL
  •  related image
    Mildly context-sensitive languages
  •  related image
    Natural languages
  •  related image
    Computer science
  •  related image
    CONTEXT FREE GRAMMARS
  •  related image
    Linguistics
  •  related image
    Context sensitive languages