View source for Splicing operation

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

A splicing rule over an alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s1102501.png" /> is a string <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s1102502.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s1102503.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s1102504.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s1102505.png" /> are two symbols not in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s1102506.png" />. With respect to such a rule, for three strings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s1102507.png" /> one writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s1102508.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s1102509.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025011.png" />, for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025012.png" />.

The pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025013.png" /> is said to splice at the sites <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025015.png" />, respectively.

A pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025016.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025017.png" /> is an alphabet and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025018.png" /> is a set of splicing rules, is called an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025020.png" />-scheme. For a language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025021.png" />, one defines

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025022.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025023.png" /></td> </tr></table>

The operation can be iterated:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025024.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025025.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025026.png" /></td> </tr></table>

On this basis, the notion of an extended <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025028.png" />-system has been introduced, [[#References|[a6]]], as a construct

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025029.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025030.png" /> is an alphabet, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025031.png" /> (terminal alphabet), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025032.png" /> (axioms), and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025033.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025035.png" /> are special symbols not in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025036.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025037.png" /> is the underlying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025039.png" />-scheme of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025040.png" />.

The language generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025042.png" /> is defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025043.png" />. For two families of languages, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025045.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025046.png" /> be the family of languages <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025047.png" /> generated by the extended <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025048.png" />-systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025049.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025050.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025051.png" />. Let FIN, REG and RE be the families of finite, regular, and recursively enumerable languages, respectively. Then:

1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025052.png" /> ([[#References|[a1]]]);

2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025053.png" /> ([[#References|[a5]]]).

The second result above was followed by many related characterizations of recursively enumerable languages by means of extended <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025054.png" />-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 [[#References|[a3]]], [[#References|[a4]]], [[#References|[a7]]].

See also [[Formal languages and automata|Formal languages and automata]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K. Culik II,   T. Harju,   "Splicing semigroups of dominoes and DNA"  ''Discrete Appl. Math.'' , '''31'''  (1991)  pp. 261–277</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  Gh. Păun,   "Splicing. A challenge to formal language theorists"  ''Bulletin of EATCS'' , '''57'''  (1995)  pp. 183–194</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  Gh. Păun,   "Regular extended H systems are computationally universal"  ''J. Automata, Languages, Combinatorics'' , '''1''' :  1  (1996)  pp. 27–36</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  Gh. Păun,   G. Rozenberg,   A. Salomaa,   "Computing by splicing"  ''Theor. Comput. Sci.'' , '''161'''  (1996)  pp. 321–336</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  Gh. Păun,   A. Salomaa,   "DNA computing based on the splicing operation"  ''Math. Japon.'' , '''43''' :  3  (1996)  pp. 607–632</TD></TR></table>