On the study of ambiguity and the trade-off between measures and ambiguity in insertion-deletion languages

Nano Communication Networks. 2011. Vol. 2. P. 106–118.

Lakshmanan K., Mahendran A., Kamala K., Khalid M.

Gene insertion and deletion are the operations that occur commonly in DNA processing
and RNA editing. Based on these operations, a computing model has been formulated
in formal language theory known as insertion–deletion systems. In this paper we study
about ambiguity issues of these systems. First, we define six levels of ambiguity for
insertion–deletion systems that are based on the components used in the derivation
such as axiom, contexts and strings. Next, we show that there are inherently i-ambiguous
insertion–deletion languages which are j-unambiguous for the combinations (i, j) ∈
{(5, 4), (4, 3), (4, 2), (3, 1), (2, 1), (1, 0), (0, 1)}. As an application, we discuss with an
example that how some of these ambiguity levels can be interpreted in gene sequences.
Further, we prove an important result that the ambiguity problem of insertion–deletion
systems is undecidable. Then, we define six new measures for insertion–deletion systems
based on used contexts and strings. Finally, we analyze the trade-off between ambiguity
levels and measures. We note that there are languages which are inherently i-ambiguous (for i = 5, 4, 2, 0) when a measure M is minimal for the languages but they are i-
unambiguous otherwise.

Keywords: insertion-deletion systems, unambiguous system, undecidability, descriptional complexity measures