Options
On the trade-off between ambiguity and measures in internal contextual grammars
Date Issued
01-01-2008
Author(s)
Lakshmanan, K.
Anand, M.
Krithivasan, Kamala
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.