Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
correctness_of_formula_propagation [2007/04/14 17:09] vkuncak |
correctness_of_formula_propagation [2007/04/14 17:19] 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 21: | Line 23: | ||
\mbox{fact}_i(w) | \mbox{fact}_i(w) | ||
\end{eqnarray*} | \end{eqnarray*} | ||
- | Let $I$ denote $\mbox{fact}_i(w)$. We have shown that $I$ is preserved across every loop iteration. Note that $sp(I,\mbox{assume}(F);c)) \rightarrow I$ corresponds to | + | Let $I$ denote $\mbox{fact}_i(w)$. We have shown |
+ | \begin{equation*} | ||
+ | sp(I, \mbox{assume}(F);c)) \rightarrow I | ||
+ | \end{equation*} | ||
+ | That is, $I$ is preserved across every loop iteration. Note that $sp(I,\mbox{assume}(F);c)) \rightarrow I$ corresponds to | ||
\begin{equation*} | \begin{equation*} | ||
I \rightarrow wp(I, \mbox{assume}(F);c) | I \rightarrow wp(I, \mbox{assume}(F);c) |