TY - JOUR
T1 - On the universality of Post and splicing systems
AU - Ferretti, C.
AU - Mauri, G.
AU - Kobayashi, S.
AU - Yokomori, T.
N1 - Funding Information:
∗Corresponding author. E-mail address: ferretti@dsi.unimi.it (C. Ferretti) 1The third and fourth authors are supported in part by \Research for the Future" Program No. JSPS-RFTF 96I00101 from the Japan Society for the Promotion of Science.
PY - 2000/1/28
Y1 - 2000/1/28
N2 - In search for a universal splicing system, in this paper we present a Post system universal for the class of Post systems, and we discuss its translation into an extended splicing system with multiplicity. We also discuss the complexity of the resulting universal splicing system, comparing our result with recent known results about the translation of universal Turing machines into splicing systems.
AB - In search for a universal splicing system, in this paper we present a Post system universal for the class of Post systems, and we discuss its translation into an extended splicing system with multiplicity. We also discuss the complexity of the resulting universal splicing system, comparing our result with recent known results about the translation of universal Turing machines into splicing systems.
KW - DNA computer
KW - Post system
KW - Splicing system
UR - http://www.scopus.com/inward/record.url?scp=0347997389&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0347997389&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(99)00097-3
DO - 10.1016/S0304-3975(99)00097-3
M3 - Article
AN - SCOPUS:0347997389
SN - 0304-3975
VL - 231
SP - 157
EP - 170
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 2
ER -