Computing by splicing

✍ Scribed by Gheorghe Păun; Grzegorz Rozenberg; Arto Salomaa

• Book ID: 104326181
• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 987 KB
• Volume: 168
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00082-5

✦ Synopsis

Computing by splicing is a new powerful tool stemming originally from molecular genetics. This new model of computing, splicing systems, is investigated here. Several variants, resulting from the use of the rules in different ways, are considered. The power of such systems with very weak structure imposed on rules turns out to be very large. Characterizations of recursively enumerable languages are obtained for many variants. In this way our study is analogous to the early studies concerning variations of Turing machines. Other classes of such splicing systems generate only regular or context-free languages (giving, in fact, characterizations of these families). With a few exceptions, we are able to obtain precise characterizations for all resulting families.