The Power of Restricted Splicing with Rules from a Regular Language
Дата
Авторы
Kari,Lila
Paun,Gheorghe
Salomaa,Arto
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
DNA recombination , splicing systems , molecular genetics , Chomsky hierarchy , regulated rewriting , abstract families of languages