Full Text:   <1257>

CLC number: TP384

On-line Access: 

Received: 2005-03-10

Revision Accepted: 2005-06-08

Crosschecked: 0000-00-00

Cited: 0

Clicked: 3407

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2005 Vol.6 No.10 P.1021~1025


Minimizing of the only-insertion insdel systems

Author(s):  MIN Yong, JIN Xiao-gang, SU Xian-chuang, PENG Bo

Affiliation(s):  AI Institute, School of Computer Science, Zhejiang University, Hangzhou 310027, China; more

Corresponding email(s):   myong@zju.edu.cn, xiaogangj@cise.zju.edu.cn

Key Words:  DNA computing, Insdel, Only insertion

MIN Yong, JIN Xiao-gang, SU Xian-chuang, PENG Bo. Minimizing of the only-insertion insdel systems[J]. Journal of Zhejiang University Science A, 2005, 6(10): 1021~1025.

@article{title="Minimizing of the only-insertion insdel systems",
author="MIN Yong, JIN Xiao-gang, SU Xian-chuang, PENG Bo",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Minimizing of the only-insertion insdel systems
%A MIN Yong
%A JIN Xiao-gang
%A SU Xian-chuang
%J Journal of Zhejiang University SCIENCE A
%V 6
%N 10
%P 1021~1025
%@ 1673-565X
%D 2005
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2005.A1021

T1 - Minimizing of the only-insertion insdel systems
A1 - MIN Yong
A1 - JIN Xiao-gang
A1 - SU Xian-chuang
A1 - PENG Bo
J0 - Journal of Zhejiang University Science A
VL - 6
IS - 10
SP - 1021
EP - 1025
%@ 1673-565X
Y1 - 2005
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2005.A1021

A more recent branch of natural computing is DNA computing. At the theoretical level, DNA computing is powerful. This is due to the fact that DNA structure and processing suggest a series of new data structures and operations, and to the fact of the massive parallelism. The insertion-deletion system (insdel system) is a DNA computing model based on two genetic operations: insertion and deletion which, working together, are very powerful, leading to characterizations of recursively enumerable languages. When designing an insdel computer, it is natural to try to keep the underlying model as simple as possible. One idea is to use either only insertion operations or only deletion operations. By helping with a weak coding and a morphism, the family INS47DEL00 is equal to the family of recursively enumerable languages. It is an open problem proposed by Martin-Vide et al. on whether or not the parameters 4 and 7 appearing here can be replaced by smaller numbers. In this paper, our positive answer to this question is that INS24DEL00 can also play the same role as insertion and deletion. We suppose that the INS24DEL00 may be the least only-insertion insdel system in this situation. We will give some reasons supporting this conjecture in our paper.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Ehrenfeucht, A., Pǎun, G., Rozenberg, G., 1998. On representing RE languages by internal contextual languages. Theoretical Computer Science, 205(1-2):61-83.

[2] Kari, L., Thierrin, G., 1996. Contextual insertion/deletion and computability. Information and Computation, 131(1):47-61.

[3] Kari, L., Pǎun, G., Thierrin, G., Yu, S., 1997. At the Crossroads of DNA Computing and Formal Languages: Characterizing RE using Insertion-Deletion Systems. Proceedings of 3rd DIMACS Workshop on DNA Based Computing, Philadelphia, p.318-333.

[4] Margenstern, M., Pǎun, G., Rogozhin, Y., Verlan, S., 2005. Context-free insertion-deletion systems. Theoretical Computer Science, 330(2):339-348.

[5] Martin-Vide, C., Pǎun, G., Salomaa, A., 1998. Characterizations of recursively enumerable language by means of insertion grammars. Theoretical Computer Science, 205(1-2):195-205.

[6] Pǎun, G., Salomaa, A., Rozenberg, G., 1998. DNA Computing: New Computing Paradigms. Springer-Verlag, p.187-216.

[7] Takahara, A., Yokomori, T., 2002. On the Computational Powers of Insertion-Deletion Systems. 8th International Meeting on DNA Based Computers, Sapporo, p.139-150.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE