| << Prev | - Up - |
How can we be sure that we really find all possible edges spanning (parts of) our input.
One central point we have not yet addressed explictly is: How can we be sure that we really find all possible edges spanning (parts of) our input. Well, the principle is simple. What we are doing is this:
We traverse our input string from left to right, and
We do not move on before we have done all that can be done at some point.
As a consequence, our chart is always complete to the left: All that could have been done there had been done. So, when we move on to some node x, we make sure that all possible edges between 0 and x are being added. Then we know, that the chart is complete up to node x when we move to x+1. As a consequence, we never have to backtrack to some earlier nodes to see whether there is anything left that has to be done. This strategy leads us systematically through the input without forgetting to add any edge.
| << Prev | - Up - |