A column that contains only right-running (left-running) items is called R-column (L-column).
Obviously, every internal column is alternately an L-column and an R-column, and the changes occur every horizontal step.
Similarly, if [K.sub.i], i [greater than] 1, is an L-column immediately after step [h.sub.t], then w([K.sub.i-1],[h.sub.t+1]) [is less than or equal to] w([K.sub.i],[h.sub.t]) [is less than or equal to] w([K.sub.i], [h.sub.t+1)].
Similarly, if [K.sub.j], j [is greater than] k, is an L-column immediately after step [h.sub.t] and w([K.sub.j, [h.sub.t]) = x, then [K.sub.j-k] is an L-column immediately after step [h.sub.t+k] and w([K.sub.j-k], [h.sub.t+k] [is less than or equal to] x.
Then w([K.sub.j], [h.sub.t]) [is less than or equal to] w([K.sub.i], [h.sub.t]) provided that j [is less than] i, i - j [is less than or equal to] 2t - 1 and [K.sub.j] is an L-column immediately after step [h.sub.t] (i.e., i and j are of different parities).
Intuitively, the R-column and the L-column that are at [K.sub.i] and [K.sub.j] after step [h.sub.t], have already "met" in the past.
Immediately after step [h.sub.t-t'], [K.sub.s+1] is an R-column and [K.sub.s] is an L-column. Hence, they are compared at step [h.sub.t-t] and therefore w([K.sub.s], [h.sub.t-t') [is less than or equal to] w([K.sub.s+t], [h.sub.t]-.sub.t').
The R-column (L-column) that resides in [K.sub.2] ([K.sub.q-2]) immediately after step [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] moves to the right (left) during the following steps.
Therefore, if during a horizontal step such an R-column [K.sub.q-i-1] is compared with an L-column [K.sub.q-i] described by the word [w.sub.i] then immediately after this step L-column [K.sub.q-i-1] is described by [w.sub.i].
In the situation when every R-column going to the right border of [P.sub.N] contains a foot of height x, we can no longer guarantee that every L-column generated on the left border contains at least ??x/2??
connect R-columns and the slanted edges inside [Z.sub.R] connect L-columns. Every R-column (L-column) is incident to the slanted edges during Step D exactly once during its movement through [Z.sub.L] ([Z.sub.R]).
Similarly, if [K.sub.j] is an L-column immediately after step [h.sub.t] j [is greater than] 1 and j [is less than or equal to] [z.sub.r], then w([K.sub.j-1], [h.sub.t+1]) [is less than or equal to] w([K.sub.j], [h.sub.t]) [is less than or equal to] w ([K.sub.j], [h.sub.t+1]).