Header menu link for other important links
X
On the trade-off between ambiguity and complexity in contextual languages
Kamala Krithivasan, Lakshmanan K, Mahendran A, Krithivasan K.
Published in
2013
Volume: 122
   
Issue: 4
Pages: 315 - 326
Abstract
Contextual grammars are introduced by Solomon Marcus in 1969 based on the fundamental concept of descriptive linguistics of insertion of strings in given contexts. Internal contextual grammars are introduced by Pǎun and Nguyen in 1980. For contextual grammars several descriptional complexity measures and levels of ambiguity have been defined. In this paper, we analyze the trade-off between ambiguity and complexity of languages generated by internal contextual grammars. The notion of a pseudo inherently ambiguous language with respect to two complexity measures is introduced and investigated. These languages can be generated by unambiguous grammars which are minimal with respect to one measure and ambiguous if they are minimal with respect to the other measure. An open problem from [15] is solved in this framework.
About the journal
JournalFundamenta Informaticae
ISSN01692968
Open AccessNo
Concepts (11)
  •  related image
    Complexity measures
  •  related image
    Contextual grammars
  •  related image
    DESCRIPTIONAL COMPLEXITY
  •  related image
    FUNDAMENTAL CONCEPTS
  •  related image
    INHERENTLY AMBIGUOUS
  •  related image
    INHERENTLY AMBIGUOUS LANGUAGES
  •  related image
    UNAMBIGUOUS
  •  related image
    UNAMBIGUOUS GRAMMAR
  •  related image
    Computational methods
  •  related image
    Information systems
  •  related image
    CONTEXT FREE GRAMMARS