Information Technology Reference
In-Depth Information
to bottom (exactly as we read a page of text). The expression (2.2) is an
ORF, strarting at “Q” (position 0) and terminating at “d” (position 7). I named
these ORFs
K-expressions
(from Karva language).
Note that this notation differs from both the postfix and prefix representa-
tions used in different GP implementations with arrays or stacks (Keith and
Martin 1994). Figure 2.1 compares Karva notation both with postfix and
prefix expressions.
K-expression:
01234567
Q*-+abcd
Prefix:
01234567
Q*+dc-ba
Postfix:
01234567
ab-cd+*Q
Figure 2.1.
Comparison of Karva notation with both postfix and prefix
representations. In all cases, the expression (2.1) is represented.
Consider another ORF, the following K-expression:
01234567890
Q*b**+baQba
(2.3)
Its expression as an ET is also very simple and straightforward. For its com-
plete expression, the rules governing the spatial distribution of functions and
terminals must be followed. First, the start of the ORF corresponds to the
root of the ET (this root, though, is at the top of the tree), forming this node
the first line of the ET. Second, depending on the number of arguments of
each element (functions may have a different number of arguments, whereas
terminals have an arity of zero), in the next line are placed as many nodes as
there are arguments to the elements in the previous line. Third, from left to
right, the new nodes are filled consecutively with the elements of the ORF.
This process is repeated until a line containing only terminals is formed. So,
for the K-expression (2.3) above, the root of the ET will be formed by “Q”,
the symbol at position 0:
Q
The square root function has only one argument, so the next line requires only
one node, which is filled with the next symbol at position 1, that is, “*”:
