The Power of Restricted Splicing with Rules from a Regular Language

Lila Kari; Gheorghe Paun; Arto Salomaa

doi:10.3217/jucs-002-04-0224

JUCS - Journal of Universal Computer Science 2(4): 224-240, doi: 10.3217/jucs-002-04-0224

The Power of Restricted Splicing with Rules from a Regular Language

Lila Kari^‡, Gheorghe Paun^§, Arto Salomaa^|

‡ Department of Mathematics University of Western Ontario, London, Ontario, Canada§ Institute of Mathematics of the Romanian Academy, Bucharest, Romania| Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland

Corresponding author: Lila Kari

This article is freely available under the J.UCS Open Content License.

Citation: Kari L, Paun G, Salomaa A (1996) The Power of Restricted Splicing with Rules from a Regular Language. JUCS - Journal of Universal Computer Science 2(4): 224-240. https://doi.org/10.3217/jucs-002-04-0224

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

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