COMPUTING BY SPLICING

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 rul es in different ways, are considered. The power of such systems with v ery weak structure imposed on rules turns out to be very large. Charac terizations of recursively enumerable languages are obtained for many variants. In this way our study is analogous to the early studies conc erning variations of Turing machines. Other classes of such splicing s ystems generate only regular or context-free languages (giving, in fac t, characterizations of these families). With a few exceptions, we are able to obtain precise characterizations for all resulting families.