Peggy Sullivan
Cut, Paste and Filter (7/7/00) ( dvi or postscript or pdf)
Discrete Applied Math., 128 (2003), no. 2-3, pp. 465-485.

We study the combined and separate effects of three parts of finite multi-test-tube cut and paste DNA computing. First, we reformulate the ideas of Csuhaj-Varju, Kari, and Paun; Freund; and Priese, Rogojine and Margenstern about multi-test-tube splicing DNA computing in terms of cutting and pasting as in Pixton's work. Pixton shows that with finite cutting and pasting only regular sets can be obtained from a finite set of initial molecules. The others listed above show that using filtering between a finite number of test-tubes, each with finite splicing, any recursively enumerable set can be obtained from finite initial contents. We confirm their result for cutting and pasting. Second, we show that when only finite pasting and filtering between tubes with finite initial contents are allowed then the result must be context free and that any context free language can be so obtained. Finally, we consider several forms of filtering and several ways of combining filtering with cutting, pasting or splicing and show that all give equivalent results.