Information Technology Reference
In-Depth Information
Ta b l e 2 . 7
The Quaternary Recombination Algorithm
XPCR
−
Recombination
(
{
α
1
,
α
2
,...
α
n
},{
β
1
,
β
2
,...
β
n
}
)=
let
Type
(
P
)=
{
η
1
,
η
2
,
η
3
,
η
4
}
;
P
:
=
in f ix
(
P
,
α
,
β
)
;
for
i
=
2
,
n
−
1
do
begin
P
:
=
PCR
(
P
,
α
,
α
i
)
;
P
:
=
PCR
(
P
,
α
i
,
¯
β
)
;
¯
P
:
=
PCR
(
P
,
α
,
β
i
)
;
¯
P
:
=
PCR
(
P
,
β
i
,
β
)
;
¯
P
:
=
PCR
(
P
,
α
,
β
)
;
end
;
output
P
.
The quaternary recombination algorithm has the additional advantage of being
equipped with a couple of special strings, called
recombination witnesses
, such that,
if they are present in the final pool then the whole library of possible recombinations
is present too. Namely, let us consider a pool
P
including the four strings of quater-
nary recombination (prefixed by the string
), then a
set
W
of stings is a
XPCR
witness
set, if when all the strings of
W
are included into
P
, then all the possible XPCR recombinations where realized from the four initial
strings. Let us call
i
-
trio-factor
any substring of three components
α
and suffixed by the string
β
γ
i
−
1
γ
i
γ
i
+
1
where
exactly two consecutive components are positive (
α
strings)ornegative(
β
strings),
then the following lemmas can be shown [30, 26].
Proposition 2.4.
The recombination according to the X PCR rule r
γ
(
γ
=
α
i
or
γ
=
β
i
for
1
n) was realized in the pool P, at the end of the quaternary recom-
bination algorithm starting with the four initial strings, if the i-trio-factor including
as component
<
i
<
γ
is present in some string of P.
Proposition 2.5.
The set consisting only of the following two strings is a X PCR
witness set (n
≥
6
): w
1
=
αα
α
β
β
α
α
...
β
and w
2
=
αβ
β
α
α
β
β
...
β
.
1
2
3
4
5
6
1
2
3
4
5
6
2.6
L-Systems and Morphogenesis
L-systems, introduced by Aristid Lindenmayer in 1968 [48, 53, 213], are grammars
with parallel rewriting. In particular,
EOL
is the class of L-systems which can be de-
fined as
CF
grammars where rules are applied, by a parallel rewriting of all the sym-
bols occurring in the string. It is really surprising that a wide class of developmental
processes can be described by suitable L-systems, possibly extended with elements
