The Power of Restricted Splicing with Rules from a Regular Language

Lila Kari (Department of Mathematics University of Western Ontario, Canada)

Gheorghe Paun (Institute of Mathematics of the Romanian Academy, Romania)

Arto Salomaa (Academy of Finland and Turku University, Department of Mathematics, Finland)

Abstract: We continue the investigations begun in [11] on the relationships between several variants of the splicing operation and usual operations with formal languages. The splicing operations are defined with respect to arbitrarily large sets of splicing rules, codified as simple languages. The closure properties of families in Chomsky hierarchy are examined in this context. Several surprising results are obtained about the generative or computing power of the splicing operation. Many important open problems are mentioned.

Keywords: Chomsky hierarchy, DNA recombination, abstract families of languages, molecular genetics, regulated rewriting, splicing systems

Categories: F.1.1, F.4.3