Direct Execution Learning Technology - Webble Technology - page 99

pattern pa 1 x 2 x 3 b 4 cca 1 x 2 x 3 x 4 c

1.1 1.1 1.1 1.1 1.2 1.2 1.2 1.2 by rule 3b

1.1 1.1 1.1 1.1 2.1 1.2 1.2 1.2 1.2 by rule 3a

1.1 1.1 1.1 1.1 2.1 3.1 3.1 1.2 1.2 1.2 1.2 3.2 3.2 by rule 3b

1.1 1.1 1.1 1.1 2.1 3.1 3.1 4.1 1.2 1.2 1.2 1.2 3.2 3.2 by rule 1

Fig. 5. Illustration of Jantke/Grieser annotations for the Lange/Wiehagen algorithm

Subsequently, the pattern is put into relation to the string s , because until
this points only the string's length has been taken into account.
In every row of figure 5 there are introduced some annotations. The process
terminates as soon as every symbol received an annotation. The particular anno-
tation u.v means that some variable x u is introduced and the symbols annotated
by u.v form some string for the v th occurring substitution of x u .
The example shown in figure 5 above results in the pattern x 1 x 2 x 3 x 4 x 1 x 3 .
Annotations introduced on some line above are dimmed out to stress the recently
introduced annotations.
Every turn of the annotation algorithm is defining some partition of the orig-
inal pattern. Each partition is a refinement of the preceding one by increasing
the number of sections or be annotating at least one previously not annotated
section. At the end of the run, the total number of sections equals l , the length
of the given input string, and all sections are annotated.
In figure 5 above, the first row is showing 4 sections after the first turn, two
of them with annotations. The second row shows 5 sections, 3 with annotations.
The third row shows 6 sections, 5 with annotations. Finally in row 4, there are
6 sections, all with annotations.
The following figure 6 for p = ax 1 bx 2 bax 2 ax 1 bx 2 ax 1 a and s = aaaaaaa with
l = 7 is used to illustrate some different phenomenon.

pattern pa 1 b 2 ba 2 a 1 b 2 a 1 a
1.1 1.1 1.1 1.1 1.2 1.2 1.2 1.2 by rule 3b

1.1 1.1 1.1 1.1 2.1 1.2 1.2 1.2 1.2 by rule 3a

1.1 1.1 1.1 1.1 2.1 3.1 1.2 1.2 1.2 1.2 3.2 by rule 3(b)i

1.1 1.1 1.1 1.1 2.1 3.1 4.1 1.2 1.2 1.2 1.2 3.2 by rule 2a

1.1 1.1 1.1 1.1 2.1 3.1 4.1 1.2 1.2 1.2 1.2 3.2 5.1 5.1 by rule 1

Fig. 6. Illustration of Jantke/Grieser annotations for the Lange/Wiehagen algorithm
showing some particular phenomenon in stage 3 of the turn-based annotation process

In the third round of the annotation process, the one-symbol substring p (6)
of the pattern p is selected for annotation because it occurs repeatedly at later
positions of p . Although it holds p (6) = p (12) and p (6) = p (14), only sub-
string p (12) gets an annotation, but not p (14). The reason is that an annota-
tion of p (14) by 3 . 3 would separate the pattern into 8 sections exceeding the
limit l =7.