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 | ||
|
sav08:galois_connection_on_lattices [2008/05/07 10:12] vkuncak |
sav08:galois_connection_on_lattices [2008/05/07 10:18] vkuncak |
||
|---|---|---|---|
| Line 20: | Line 20: | ||
| ===== 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) | ||
| Define $sp^\#$ using $\alpha$ and $\gamma$: | Define $sp^\#$ using $\alpha$ and $\gamma$: | ||
| Line 27: | Line 35: | ||
| \] | \] | ||
| ++++ | ++++ | ||
| + | |||
| + | ===== 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". | ||