Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav08:galois_connection_on_lattices [2008/05/07 10:14] vkuncak |
sav08:galois_connection_on_lattices [2015/04/21 17:30] (current) |
||
---|---|---|---|
Line 18: | Line 18: | ||
* $\alpha$ is a [[wk>surjective function]] | * $\alpha$ is a [[wk>surjective function]] | ||
* $\gamma$ is an [[wk>injective function]] | * $\gamma$ is an [[wk>injective function]] | ||
+ | |||
===== Using Galois Connection ===== | ===== Using Galois Connection ===== | ||
+ | |||
+ | Terminology: | ||
+ | * $C$ - concrete domain | ||
+ | * $A$ - abstract domain | ||
+ | * $\gamma$ - concretization function | ||
+ | * $\alpha$ - abstraction function | ||
+ | * $sp$ - (the usual) strongest postcondition (or just "strongest post"), also called | ||
+ | * $sp^{\#}$ - abstract post, abstract transformer (transforms one abstract element into another) | ||
+ | |||
+ | Abstraction function for sign analysis. | ||
Define $sp^\#$ using $\alpha$ and $\gamma$: | Define $sp^\#$ using $\alpha$ and $\gamma$: | ||
++++| | ++++| | ||
- | \[ | + | \begin{equation*} |
sp^\#(a,r) = \alpha(sp(\gamma(a),r) | sp^\#(a,r) = \alpha(sp(\gamma(a),r) | ||
- | \] | + | \end{equation*} |
++++ | ++++ | ||
===== Best Abstract Transformer ===== | ===== Best Abstract Transformer ===== | ||
+ | |||
+ | $sp^{\#}$ can in general be arbitrarily precise while preserving correctness. | ||
+ | |||
+ | Given $\gamma$, we would like $sp^{\#}$ to be as precise as possible while being correct. | ||
+ | |||
+ | The most precise $sp^{\#}$ is called "best abstract transformer". | ||
+ | |||
+ | If $\alpha(\gamma(a)) = a$, then $sp^{\#}$ defined using $\alpha$ and $\gamma$ is the most precise one (given the abstract domain and particular blocks in the control-flow graph). | ||
+ |