Information Technology Reference
In-Depth Information
{
uxwxv
}⇒{
uxv,
•
wx
}
,
q
v
.
This constrains intramolecular
recombination within
uxwxv
to occur only if the restrictions of the splicing
scheme concerning
x
are fulfilled (i.e., the first occurrence of
x
is preceded by
p
and followed by
q
, and its second occurrence is preceded by
p
and followed
by
q
).
Similarly, if
(p,x,q)
∼
(p
,x,q
)
, then we define
contextual intermolecu-
lar recombination
as
u
p,w
qw
w
p
,v
where
u
=
=
=
=
{
uxv,
•
wx
}⇒{
uxwxv
}
,
where
u
=
u
p, v
=
qv
,w
=
w
p
=
q
w
.
Informally, intermolecular
recombination between the linear strand
uxv
and the circular strand
•
wx
may
take place only if the occurrence of
x
in the linear strand is flanked by
p
and
q
and
its occurrence in the circular strand is flanked by
p
and
q
. Note that sequences
p, x, q, p
,q
are nonempty and that both contextual intra- and intermolecular
recombinations are reversible by introducing pairs
(p,x,q
)
(p
,x,q)
in
.
The operations defined in the preceding section are particular cases of contex-
tual recombinations, where all the contexts are empty [i.e,
(
∼
∼
λ
,x,
λ
)
∼
(
λ
,x,
λ
)
∈ Σ
+
]. This would correspond to the case where recombination may
occur between every two pointers, regardless of their contexts.
for all
x
DEFINITION 7 A guided recombination system is a construct
R
=
(
Σ
,
∼
,A)
where
(
Σ
,
∼
)
is a splicing scheme, and
A
∈ Σ
+
is a linear string called the
axiom
.
Those strands which, by repeated contextual recombinations with initial and
intermediate strands eventually produce the axiom, form the language of the
guided recombination system,
L
a
(R)
.
L
a
(R)
thus denotes the multiset of words
w
∈ Σ
∗
with the property that, if present initially in at least
k
copies, are able
to produce the axiom
A
by a series of contextual recombinations. (A multiset
is a set where to each element is associated a multiplicity. Operations applied
to elements of a multiset change their multiplicities. After an operation, the
multiplicities of the operation inputs decrease by one, while the multiplicity of
the operation output increases by one. The need of multisets for modeling is
justified in Landweber and Kari [9].)
Let
L
be a language over
T
∗
accepted by TM
=
Σ ∪{
}
THEOREM 3
(S,
#
,P)
.
π ∈ Σ
∗
, depending on
L
, and a
guided recombination system,
R
, such that a word
w
over
T
∗
is in
L
if and only
if #
6
s
0
w
#
6
Σ
, a sequence
Then there exist an alphabet
belongs to
L
a
(R)
for some
k
≥
1.
The idea of the proof is as follows. Consider that the rules of
P
are ordered
in an arbitrary fashion and numbered. Thus, if TM has
m
rules, a rule is of the
form
i
:
u
i
−→
v
i
where 1
π
≤
i
≤
m
.
