Bio-Inspired Models of Network, Information, and Computing Systems. 5th International ICST Conference, BIONETICS 2010, Boston, USA, December 1-3, 2010, Revised Selected Papers

Research Article

On the Ambiguity and Complexity Measures of Insertion-Deletion Systems

Download
493 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-32615-8_41,
        author={Kamala Krithivasan and Lakshmanan Kuppusamy and Anand Mahendran and Khalid M.},
        title={On the Ambiguity and Complexity Measures of Insertion-Deletion Systems},
        proceedings={Bio-Inspired Models of Network, Information, and Computing Systems. 5th International ICST Conference, BIONETICS 2010, Boston, USA, December 1-3, 2010, Revised Selected Papers},
        proceedings_a={BIONETICS},
        year={2012},
        month={10},
        keywords={DNA processing insertion-deletion systems inherently ambiguous languages unambiguous grammar complexity measures},
        doi={10.1007/978-3-642-32615-8_41}
    }
    
  • Kamala Krithivasan
    Lakshmanan Kuppusamy
    Anand Mahendran
    Khalid M.
    Year: 2012
    On the Ambiguity and Complexity Measures of Insertion-Deletion Systems
    BIONETICS
    Springer
    DOI: 10.1007/978-3-642-32615-8_41
Kamala Krithivasan1,*, Lakshmanan Kuppusamy2,*, Anand Mahendran2,*, Khalid M.2
  • 1: IIT Madras
  • 2: VIT University
*Contact email: kamala@iitm.ac.in, klakshma@vit.ac.in, manand@vit.ac.in

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 systems. In this paper we study about ambiguity and complexity measures of these systems. First, we define the various levels of ambiguity ( = 0,1,2,3,4,5) for insertion-deletion systems. Next, we show that there are inherently -ambiguous insertion-deletion languages which are -unambiguous for the combinations (, ) ∈ {(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  − ,  − ,  −  for insertion-deletion systems and analyze the trade-off between the newly defined ambiguity levels and complexity measures.