Accepting multiple splicing systems

Abstract

We introduce an accepting splicing system based on a type of splicing, multiple splicing, which has never considered so far for accepting systems. This type of splicing differs from the usual operation in that several (not necessarily distinct) rules can be applied simultaneously to the same string. We first consider accepting multiple splicing systems where the number of splicing sites is a predefined constant. We prove that this model is computationally complete, if the constant is 2, by simulating a 2-tag system. Moreover, we show that the simulation is time-complexity preserving, and discuss also the descriptional complexity of the accepting splicing system given by our construction. We then consider the accepting multiple splicing systems where the number of sites has either an upper bound or a lower bound. The computational power of these systems is also investigated. We finally discuss some open problems.

Keywords

• DNA computing
• Molecular computing
• Splicing
• Multiple splicing
• Accepting multiple splicing system