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 | ||
|
sav07_lecture_3_skeleton [2007/03/20 14:54] vkuncak |
sav07_lecture_3_skeleton [2007/03/20 17:23] vkuncak |
||
|---|---|---|---|
| Line 2: | Line 2: | ||
| ===== Converting programs (with simple values) to formulas ===== | ===== Converting programs (with simple values) to formulas ===== | ||
| + | |||
| Line 20: | Line 21: | ||
| * correct | * correct | ||
| * efficient | * efficient | ||
| - | * create formulas that we can prove later | + | * create formulas that we can effectively prove later |
| + | |||
| + | What exactly do we prove about the formula R( c ) ? | ||
| + | |||
| + | We prove that this formula is **valid** | ||
| + | |||
| + | R( c ) -> error=false | ||
| Line 64: | Line 71: | ||
| when c is a basic command. | when c is a basic command. | ||
| + | |||
| Line 84: | Line 92: | ||
| We can apply these rules to reduce the size of formulas. | We can apply these rules to reduce the size of formulas. | ||
| + | |||
| + | ==== Symbolic execution ==== | ||
| + | |||
| + | Symbolic execution converts programs into formulas by going forward. It is therefore somewhat analogous to the way an [[interpreter]] for the language would work. It is based on the notion of strongest postcondition. | ||
| + | |||
| + | |||
| + | ==== Weakest preconditions ==== | ||
| + | |||
| + | While symbolic execution computes formula by going forward along the program syntax tree, weakest precondition computes formula by going backward. | ||
| + | |||
| + | ===== Proving quantifier-free linear arithmetic formulas ===== | ||
| ==== Papers ==== | ==== Papers ==== | ||