Research Article
On the Ambiguity and Complexity Measures of Insertion-Deletion Systems
@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
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.
