On the power of the splicing operation1

Publisher Website
Google Scholar
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.

This publication has 5 references indexed in Scilit: