Restricted use of the splicing operation¹

Research supported by the Academy of Finland. project 11281, and the ESPRIT Basic Research Working Group ASMICS 11.

Abstract

Splicing is a new powerful tool, stemming originally from molecular genetics but investigated extensively also in language theory. In this paper we investigate variants of splicing inspired partly by regulating mechanisms customarily studied in language theory, partly by imposing restrictions on the pairs to be spliced or on the result of splicing. The Chomsky hierarchy constitutes a very suitable test bed for the resulting families, because it is classical and well understood. In contrast to the usual, nonrestricted splicing, we find several cases when the families of regular or of context-free languages are not closed under the new types of splicing. On the other hand, our results give new characterizations for families in the Chomsky hierarchy and for closure properties in general.

Keywords:

• DNA recombination
• splicing systems
• molecular genetics
• Chomsky hierarcky,regulated rewriting, abstract families of languages

C.R. CATEGORIES:

• F.4.3
• F.1.1

Research supported by the Academy of Finland. project 11281, and the ESPRIT Basic Research Working Group ASMICS 11.

Research supported by the Academy of Finland. project 11281, and the ESPRIT Basic Research Working Group ASMICS 11.

Notes

Research supported by the Academy of Finland. project 11281, and the ESPRIT Basic Research Working Group ASMICS 11.