Namespaces
Variants
Actions

Difference between revisions of "Splicing operation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fix tex)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
s1102501.png
 +
$#A+1 = 50 n = 0
 +
$#C+1 = 50 : ~/encyclopedia/old_files/data/S110/S.1100250 Splicing operation
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
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 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" />.
+
A splicing rule over an alphabet $  V $
 +
is a string $  r = u _ {1} \# u _ {2} \$ u _ {3} \# u _ {4} $,  
 +
where $  u _ {1} ,u _ {2} ,u _ {3} ,u _ {4} \in V  ^ {*} $
 +
and $  \# $,  
 +
$  \$ $
 +
are two symbols not in $  V $.  
 +
With respect to such a rule, for three strings $  x,y,z \in V  ^ {*} $
 +
one writes $  ( x,y ) \vdash _ {r} z $
 +
if $  x = x _ {1} u _ {1} u _ {2} x _ {2} $,  
 +
$  y = y _ {1} u _ {3} u _ {4} y _ {2} $,  
 +
$  z = x _ {1} u _ {1} u _ {4} y _ {2} $,  
 +
for some $  x _ {1} ,x _ {2} ,y _ {1} ,y _ {2} \in V  ^ {*} $.
  
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.
+
The pair $  x,y $
 +
is said to splice at the sites $  u _ {1} u _ {2} $,  
 +
$  u _ {3} u _ {4} $,  
 +
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
+
A pair $  \sigma = ( V, R ) $,  
 +
where $  V $
 +
is an alphabet and $  R \subseteq V  ^ {*} \# V  ^ {*} \$ V  ^ {*} \# V  ^ {*} $
 +
is a set of splicing rules, is called an $  H $-
 +
scheme. For a language $  L \subseteq V  ^ {*} $,  
 +
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>
+
$$
 +
\sigma ( L ) =
 +
$$
  
<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>
+
$$
 +
=  
 +
\left \{ {z \in V  ^ {*} } : {( x,y ) \vdash _ {r} z  \textrm{ for  some  }  x,y \in L,  r \in R } \right \} .
 +
$$
  
 
The operation can be iterated:
 
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>
+
$$
 +
\sigma  ^ {0} ( L ) = L,
 +
$$
  
<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>
+
$$
 +
\sigma ^ {i + 1 } ( L ) = \sigma  ^ {i} ( L ) \cup \sigma ( \sigma  ^ {i} ( L ) ) , \quad i \geq  0,
 +
$$
  
<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>
+
$$
 +
\sigma  ^ {*} ( L ) = \cup _ {i \geq  0 } \sigma  ^ {i} ( L ) .
 +
$$
  
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
+
On this basis, the notion of an extended $  H $-
 +
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>
+
$$
 +
\gamma = ( V,T,A,R ) ,
 +
$$
  
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" />.
+
where $  V $
 +
is an alphabet, $  T \subseteq V $(
 +
terminal alphabet), $  A \subseteq V  ^ {*} $(
 +
axioms), and $  R \subseteq V  ^ {*} \# V  ^ {*} \$ V  ^ {*} \# V  ^ {*} $,  
 +
where $  \# $,  
 +
$  \$ $
 +
are special symbols not in $  V $;  
 +
$  \sigma = ( V,R ) $
 +
is the underlying $  H $-
 +
scheme of $  \gamma $.
  
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:
+
The language generated by $  \gamma $
 +
is defined by $  L ( \gamma ) = \sigma  ^ {*} ( A ) \cap T  ^ {*} $.  
 +
For two families of languages, $  F _ {1} $,  
 +
$  F _ {2} $,  
 +
let $  { \mathop{\rm EH} } ( F _ {1} ,F _ {2} ) $
 +
be the family of languages $  L ( \gamma ) $
 +
generated by the extended $  H $-
 +
systems $  \gamma = ( V,T,A,R ) $
 +
with $  A \in F _ {1} $,  
 +
$  R \in F _ {2} $.  
 +
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]]]);
+
1) $  { \mathop{\rm EH} } ( { \mathop{\rm REG} } , { \mathop{\rm FIN} } ) = { \mathop{\rm REG} } $([[#References|[a1]]]);
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110250/s11025053.png" /> ([[#References|[a5]]]).
+
2) $  { \mathop{\rm EH} } ( { \mathop{\rm FIN} } , { \mathop{\rm REG} } ) = { \mathop{\rm RE} } $([[#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]]].
+
The second result above was followed by many related characterizations of recursively enumerable languages by means of extended $  H $-
 +
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]].
 
See also [[Formal languages and automata|Formal languages and automata]].

Latest revision as of 19:55, 17 December 2020


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 $ V $ is a string $ r = u _ {1} \# u _ {2} \$ u _ {3} \# u _ {4} $, where $ u _ {1} ,u _ {2} ,u _ {3} ,u _ {4} \in V ^ {*} $ and $ \# $, $ \$ $ are two symbols not in $ V $. With respect to such a rule, for three strings $ x,y,z \in V ^ {*} $ one writes $ ( x,y ) \vdash _ {r} z $ if $ x = x _ {1} u _ {1} u _ {2} x _ {2} $, $ y = y _ {1} u _ {3} u _ {4} y _ {2} $, $ z = x _ {1} u _ {1} u _ {4} y _ {2} $, for some $ x _ {1} ,x _ {2} ,y _ {1} ,y _ {2} \in V ^ {*} $.

The pair $ x,y $ is said to splice at the sites $ u _ {1} u _ {2} $, $ u _ {3} u _ {4} $, respectively.

A pair $ \sigma = ( V, R ) $, where $ V $ is an alphabet and $ R \subseteq V ^ {*} \# V ^ {*} \$ V ^ {*} \# V ^ {*} $ is a set of splicing rules, is called an $ H $- scheme. For a language $ L \subseteq V ^ {*} $, one defines

$$ \sigma ( L ) = $$

$$ = \left \{ {z \in V ^ {*} } : {( x,y ) \vdash _ {r} z \textrm{ for some } x,y \in L, r \in R } \right \} . $$

The operation can be iterated:

$$ \sigma ^ {0} ( L ) = L, $$

$$ \sigma ^ {i + 1 } ( L ) = \sigma ^ {i} ( L ) \cup \sigma ( \sigma ^ {i} ( L ) ) , \quad i \geq 0, $$

$$ \sigma ^ {*} ( L ) = \cup _ {i \geq 0 } \sigma ^ {i} ( L ) . $$

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

$$ \gamma = ( V,T,A,R ) , $$

where $ V $ is an alphabet, $ T \subseteq V $( terminal alphabet), $ A \subseteq V ^ {*} $( axioms), and $ R \subseteq V ^ {*} \# V ^ {*} \$ V ^ {*} \# V ^ {*} $, where $ \# $, $ \$ $ are special symbols not in $ V $; $ \sigma = ( V,R ) $ is the underlying $ H $- scheme of $ \gamma $.

The language generated by $ \gamma $ is defined by $ L ( \gamma ) = \sigma ^ {*} ( A ) \cap T ^ {*} $. For two families of languages, $ F _ {1} $, $ F _ {2} $, let $ { \mathop{\rm EH} } ( F _ {1} ,F _ {2} ) $ be the family of languages $ L ( \gamma ) $ generated by the extended $ H $- systems $ \gamma = ( V,T,A,R ) $ with $ A \in F _ {1} $, $ R \in F _ {2} $. Let FIN, REG and RE be the families of finite, regular, and recursively enumerable languages, respectively. Then:

1) $ { \mathop{\rm EH} } ( { \mathop{\rm REG} } , { \mathop{\rm FIN} } ) = { \mathop{\rm REG} } $([a1]);

2) $ { \mathop{\rm EH} } ( { \mathop{\rm FIN} } , { \mathop{\rm REG} } ) = { \mathop{\rm RE} } $([a5]).

The second result above was followed by many related characterizations of recursively enumerable languages by means of extended $ H $- 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
How to Cite This Entry:
Splicing operation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Splicing_operation&oldid=13028
This article was adapted from an original article by Gh. Păun (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article