On Computational Power of Insertion-Deletion Systems without Using Contexts

Sadaki HIROSE  Satoshi OKAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.8   pp.1993-1995
Publication Date: 2005/08/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.8.1993
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Automata and Formal Language Theory
Keyword: 
Insertion-Deletion system,  DNA computing,  formal language,  automaton,  

Full Text: PDF>>
Buy this Article




Summary: 
An Insertion-Deletion system, first introduced in [1], is a theoretical computing model in the DNA computing framework based on insertion and deletion operations. When insertion and deletion operations work together, as expected, they are very powerful. In fact, it has been shown that even the very restricted Insertion-Deletion systems can characterize the class of recursively enumerable languages [1]-[4]. In this paper, we investigate the computational power of Insertion-Deletion systems and show that they preserve the computational universality without using contexts.