Full Text:
<2755>
CLC number: TP384
On-line Access:
Received: 2005-03-10
Revision Accepted: 2005-06-08
Crosschecked: 0000-00-00
Cited: 0
Clicked: 5295
Minimizing of the only-insertion insdel systems
| |||||||||||||
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",
volume="6",
number="10",
pages="1021-1025",
year="2005",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2005.A1021"
}
%0 Journal Article
%T Minimizing of the only-insertion insdel systems
%A MIN Yong
%A JIN Xiao-gang
%A SU Xian-chuang
%A PENG Bo
%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
TY - JOUR
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
Abstract: 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.
[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
<1>