TY - JOUR
T1 - Multiple splicing systems and the universal computability
AU - Kobayashi, Satoshi
AU - Sakakibara, Yasubumi
N1 - Funding Information:
This work was supported in part by “Research for the Future” Program No. JSPS-RFTF 96I00101 from the Japan Society for the Promotion of Science. The Drst author was supported in part by Grants-in-Aid for ScientiDc Research No. 09878059 from the Ministry of Education, Science and Culture, Japan.
PY - 2001
Y1 - 2001
N2 - We propose a new extension of splicing systems, called multiple splicing systems, based on a kind of logic grammars. First, we introduce a class of Elementary formal systems, called simple H-form EFS, and show that its generative power is equivalent to the class of basic splicing systems (the original Head's splicing system) and is more adequate as a representation device for formal languages. Next, we gradually extend the simple class of EFSs and get a very natural extension of splicing systems, multiple splicing systems. We show that multiple splicing systems have universal computability.
AB - We propose a new extension of splicing systems, called multiple splicing systems, based on a kind of logic grammars. First, we introduce a class of Elementary formal systems, called simple H-form EFS, and show that its generative power is equivalent to the class of basic splicing systems (the original Head's splicing system) and is more adequate as a representation device for formal languages. Next, we gradually extend the simple class of EFSs and get a very natural extension of splicing systems, multiple splicing systems. We show that multiple splicing systems have universal computability.
KW - Computability
KW - DNA computing
KW - Splicing system
UR - http://www.scopus.com/inward/record.url?scp=0034899857&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0034899857&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(00)00211-5
DO - 10.1016/S0304-3975(00)00211-5
M3 - Article
AN - SCOPUS:0034899857
SN - 0304-3975
VL - 264
SP - 3
EP - 23
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1
ER -