For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Computational Power of Insertion-Deletion Systems without Using Contexts
Sadaki HIROSE Satoshi OKAWA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/08/01
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Automata and Formal Language Theory
Insertion-Deletion system, DNA computing, formal language, automaton,
Full Text: PDF>>
An Insertion-Deletion system, first introduced in , 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 -. In this paper, we investigate the computational power of Insertion-Deletion systems and show that they preserve the computational universality without using contexts.