Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
correctness_of_formula_propagation [2007/04/14 17:08] vkuncak |
correctness_of_formula_propagation [2007/04/14 17:17] vkuncak |
||
---|---|---|---|
Line 4: | Line 4: | ||
Using an example of a single loop, we explain that if the analysis terminates then it computes an inductive invariant weaker than the initial formula. | Using an example of a single loop, we explain that if the analysis terminates then it computes an inductive invariant weaker than the initial formula. | ||
+ | |||
+ | By induction, to prove that property holds after any number of loop iterations, we show that it holds initially and that it is preserved by each loop iteration. | ||
Consider a loop | Consider a loop | ||
Line 13: | Line 15: | ||
{{loop.png}} | {{loop.png}} | ||
- | When the analysis terminates, we have $\mbox{fact}_{i+1}(a) \rightarrow \mbox{fact}_i(a)$. We therefore have | + | When the analysis terminates, we have $\mbox{fact}_{i+1}(w) \rightarrow \mbox{fact}_i(w)$. We therefore have |
\begin{eqnarray*} | \begin{eqnarray*} | ||
sp(\mbox{fact}_i(w), \mbox{assume}(F);c) \rightarrow \\ | sp(\mbox{fact}_i(w), \mbox{assume}(F);c) \rightarrow \\ |