Header menu link for other important links
X
On the trade-off between ambiguity and measures in internal contextual grammars
Lakshmanan K., , Krithivasan K.
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