Splicing operation

A formal model of the recombinant behaviour of DNA sequences under the influence of restriction enzymes and ligases; it was introduced in [a2].

A splicing rule over an alphabet is a string , where and , are two symbols not in . With respect to such a rule, for three strings one writes if , , , for some .

The pair is said to splice at the sites , , respectively.

A pair , where is an alphabet and is a set of splicing rules, is called an -scheme. For a language , one defines

The operation can be iterated:

On this basis, the notion of an extended -system has been introduced, [a6], as a construct

where is an alphabet, (terminal alphabet), (axioms), and , where , are special symbols not in ; is the underlying -scheme of .

The language generated by is defined by . For two families of languages, , , let be the family of languages generated by the extended -systems with , . Let FIN, REG and RE be the families of finite, regular, and recursively enumerable languages, respectively. Then:

1) ([a1]);

2) ([a5]).

The second result above was followed by many related characterizations of recursively enumerable languages by means of extended -systems with finite sets of axioms and splicing rules, with the splicing operation controlled in various ways. (This theoretically proves the possibility of constructing universal "DNA computers" based on splicing.) Details can be found in [a3], [a4], [a7].

See also Formal languages and automata.

References

[a1]	K. Culik II, T. Harju, "Splicing semigroups of dominoes and DNA" Discrete Appl. Math. , 31 (1991) pp. 261–277
[a2]	T. Head, "Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors" Bull. Math. Biology , 49 (1987) pp. 737–759
[a3]	T. Head, Gh. Păun, D. Pixton, "Language theory and molecular genetics. Generative mechanisms suggested by DNA recombination" G. Rozenberg (ed.) A. Salomaa (ed.) , Handbook of Formal Languages , Springer (1997)
[a4]	Gh. Păun, "Splicing. A challenge to formal language theorists" Bulletin of EATCS , 57 (1995) pp. 183–194
[a5]	Gh. Păun, "Regular extended H systems are computationally universal" J. Automata, Languages, Combinatorics , 1 : 1 (1996) pp. 27–36
[a6]	Gh. Păun, G. Rozenberg, A. Salomaa, "Computing by splicing" Theor. Comput. Sci. , 161 (1996) pp. 321–336
[a7]	Gh. Păun, A. Salomaa, "DNA computing based on the splicing operation" Math. Japon. , 43 : 3 (1996) pp. 607–632