Header menu link for other important links
X
On the ambiguity and complexity measures of insertion-deletion systems
Kamala Krithivasan, Krithivasan K, , Mahendran A, Khalid M.
Published in
2012
Volume: 87 LNICST
   
Pages: 425 - 439
Abstract
In DNA processing and RNA editing, gene insertion and deletion are considered as the basic operations. Based on the above evolutionary transformations, a computing model has been formulated in formal language theory known as insertion-deletion systems. In this paper we study about ambiguity and complexity measures of these systems. First, we define the various levels of ambiguity (i = 0,1,2,3,4,5) for insertion-deletion systems. Next, we show that there are inherently i-ambiguous insertion-deletion languages which are j-unambiguous for the combinations (i, j) ∈ {(5,4), (4,2), (3,1), (3,2), (2,1),(0,1)}. Further, We prove an important result that the ambiguity problem of insertion-deletion system is undecidable. Finally, we define three new complexity measures TLength - Con, TLength - Ins, TLength - Del for insertion-deletion systems and analyze the trade-off between the newly defined ambiguity levels and complexity measures. © 2012 ICST Institute for Computer Science, Social Informatics and Telecommunications Engineering.
About the journal
JournalLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering
ISSN18678211
Open AccessNo
Concepts (13)
  •  related image
    Basic operation
  •  related image
    Complexity measures
  •  related image
    Computing model
  •  related image
    EVOLUTIONARY TRANSFORMATIONS
  •  related image
    FORMAL LANGUAGE THEORY
  •  related image
    INHERENTLY AMBIGUOUS LANGUAGES
  •  related image
    Insertion-deletion systems
  •  related image
    RNA EDITING
  •  related image
    UNAMBIGUOUS GRAMMAR
  •  related image
    Formal languages
  •  related image
    Genes
  •  related image
    RNA
  •  related image
    CONTEXT FREE GRAMMARS