Header menu link for other important links
X
On the trade-off between ambiguity and measures in internal contextual grammars
Kamala Krithivasan
Published in University of Prince Edward Island
2008
Pages: 216 - 223
Abstract
Several complexity measures and levels of ambiguity were defined for internal contextual grammars. In this paper, we consider the following trade-off between ambiguity and measures of these grammars. When a minimal complexity measure M1 is chosen for a language L, the corresponding grammar is ambiguous. Conversely, when an unambiguous grammar is chosen for L, the grammar is not minimal in M1. We introduce a new notion in formal language theory, named pseudo inherently ambiguous languages.
About the journal
JournalDescriptional Complexity of Formal Systems - 10th International Workshop, DCFS 2008
PublisherUniversity of Prince Edward Island
Open AccessNo
Concepts (8)
  •  related image
    Dispersion compensation
  •  related image
    Formal languages
  •  related image
    Complexity measures
  •  related image
    Contextual grammars
  •  related image
    FORMAL LANGUAGE THEORY
  •  related image
    INHERENTLY AMBIGUOUS LANGUAGES
  •  related image
    UNAMBIGUOUS GRAMMAR
  •  related image
    CONTEXT FREE GRAMMARS