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

• Published in: Nano communication networks 2011-06, Vol.2 (2), p.106-118
• Main Authors: Kuppusamy, Lakshmanan, Mahendran, Anand, Krithivasan, Kamala, Mohammed, Khalid
• Format: Article
• Language: English
• Subjects: Bio-molecular structures; Descriptional complexity measures; Inherently ambiguous languages; Insertion–deletion systems; Unambiguous system; Undecidability
• ISSN: 1878-7789; 1878-7797
• DOI: 10.1016/j.nancom.2011.06.001

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.