On the power of the splicing operation¹

¹Research supported by the Academy of Finland, project 11281

Abstract

We prove that each recursively enumerable language can be written as the image through a restricted morphism of the intersection of a regular language with the language associated to a splicing system with finitely many rules, starting from finitely many initial words, and with limitations on the number of copies of each initial or subsequently generated word. A proof of the membership undecidability for such splicing systems is obtained in this way (much shorter than the proof in [4]), as well as a series of consequences concerning the generative power of splicing systems.

Keywords:

• DNA
• splicing system
• recursively enumerable language
• undecidability

C.R. Categories:

• F.4.3
• F.1.1

¹Research supported by the Academy of Finland, project 11281

¹Research supported by the Academy of Finland, project 11281

Notes

¹Research supported by the Academy of Finland, project 11281