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 | ||
sav07_lecture_6 [2007/04/15 23:59] mirco.dotta |
sav07_lecture_6 [2007/04/16 10:03] mirco.dotta |
||
---|---|---|---|
Line 125: | Line 125: | ||
\end{equation*} | \end{equation*} | ||
where $\theta$ is the most general unifier of $A_1$ and $A_2$. | where $\theta$ is the most general unifier of $A_1$ and $A_2$. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
Line 162: | Line 167: | ||
by: ¬(∃x.F) <=> ∀x.¬F and ¬(∀x.F) <=> ∃x.¬F | by: ¬(∃x.F) <=> ∀x.¬F and ¬(∀x.F) <=> ∃x.¬F | ||
∀x.∃y.R(x,y) ∧ ∀y.∃x.¬R(x,y)\\ | ∀x.∃y.R(x,y) ∧ ∀y.∃x.¬R(x,y)\\ | ||
- | by: Skolenization | + | by: Skolemization |
{R(x, s1(x)), ¬R(s2(y),y)}\\ | {R(x, s1(x)), ¬R(s2(y),y)}\\ | ||
by: Unification s1(x)=y and x=s2(y) then s1(s2(y))=y | by: Unification s1(x)=y and x=s2(y) then s1(s2(y))=y | ||
by: Adding a constant 'a' | by: Adding a constant 'a' | ||
R.{s1,s2,a} = L \\ | R.{s1,s2,a} = L \\ | ||
+ | \\ | ||
+ | Term(L) = {a, s1(a), s2(a), s1(s1(a)), ...} \\ | ||
\\ | \\ | ||
[R]e<sub>T</sub> = {(t,s1(t)) | t ∈ Term(L)} where e<sub>T</sub>: F => {true, false} and T => Term(L)\\ | [R]e<sub>T</sub> = {(t,s1(t)) | t ∈ Term(L)} where e<sub>T</sub>: F => {true, false} and T => Term(L)\\ | ||
Line 178: | Line 185: | ||
∀t ∈ Term(L) ¬[R(s2(y),y) ] R(s2(y),y)]e<sub>T[y:=t]</sub> \\ | ∀t ∈ Term(L) ¬[R(s2(y),y) ] R(s2(y),y)]e<sub>T[y:=t]</sub> \\ | ||
\\ | \\ | ||
+ | [R]e<sub>T</sub> = {(a,s1(a)), (s1(a),s1(s1(a))), (s2(a), s2(s2(a))), ...} \\ | ||
\\ | \\ | ||
+ | Then we should find a pair (tx,ty) s.t. (tx,ty) ∉ [R]. A possible counter-example is (tx,a) ∉ [R], ∀tx. | ||
+ | The fact that we have found a counter-example imply that the initial formula is invalid.\\ | ||
\\ | \\ | ||
Consider case where R denotes less than relation on integers and Ev denotes that integer is even | Consider case where R denotes less than relation on integers and Ev denotes that integer is even | ||
Line 335: | Line 345: | ||
Simple example with small ascending chains but large size: constant propagation. | Simple example with small ascending chains but large size: constant propagation. | ||
+ | |||
==== Example analyses ==== | ==== Example analyses ==== | ||
Line 342: | Line 353: | ||
+ | ==== References ==== | ||
+ | * A wonderful tutorial by Prof. Cousot, explaining in fairly simple language what abstract interpretation is all about. [[http://www.di.ens.fr/~cousot/COUSOTtalks/VMCAI05_TOOLS.shtml|Tutorial Abstract Interpretation]] |