Header menu link for other important links
X
On the study of ambiguity and the trade-off between measures and ambiguity in insertion-deletion languages
Kamala Krithivasan, , Mahendran A, Krithivasan K, Mohammed K.
Published in
2011
Volume: 2
   
Issue: 2-3
Pages: 106 - 118
Abstract
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. © 2011.
About the journal
JournalNano Communication Networks
ISSN18787789
Open AccessNo
Concepts (10)
  •  related image
    BIO-MOLECULAR STRUCTURES
  •  related image
    DESCRIPTIONAL COMPLEXITY
  •  related image
    INHERENTLY AMBIGUOUS LANGUAGES
  •  related image
    Insertion-deletion systems
  •  related image
    UNAMBIGUOUS SYSTEM
  •  related image
    Undecidability
  •  related image
    CONTEXT FREE GRAMMARS
  •  related image
    Formal languages
  •  related image
    RNA
  •  related image
    Genes