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/18 19:55] vkuncak |
sav07_lecture_3_skeleton [2007/03/20 14:10] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| + | ====== Lecture 3 (Skeleton) ====== | ||
| + | |||
| + | Recall that we can | ||
| + | * represent programs using guarded command language, e.g. desugaring of 'if' into non-deterministic choice and assume | ||
| + | * give meaning to guarded command language statements as relations | ||
| + | * we can represent relations using set comprehensions; if our program has two state components, we can represent its meaning as | ||
| + | <latex> | ||
| + | \{((x_0,y_0),(x,y)) \mid F \} | ||
| + | </latex> | ||
| + | where F is some formula that mentions x,y,x_0,y_0. | ||
| + | |||
| + | Our goal is to compute this formula. | ||
| + | |||
| + | |||
| ==== Papers ==== | ==== Papers ==== | ||
| * Verification condition generation in Spec#: http://research.microsoft.com/~leino/papers/krml157.pdf | * Verification condition generation in Spec#: http://research.microsoft.com/~leino/papers/krml157.pdf | ||
| + | * Loop invariant inference for set algebra formulas: {{hob-tcs.pdf}} | ||
| + | * Induction-iteration method for machine code checking: http://www.cs.wisc.edu/wpis/papers/pldi00.ps | ||
| + | |||
| * Presburger Arithmetic (PA) bounds: {{papadimitriou81complexityintegerprogramming.pdf}} | * Presburger Arithmetic (PA) bounds: {{papadimitriou81complexityintegerprogramming.pdf}} | ||
| * Specializing PA bounds: http://www.lmcs-online.org/ojs/viewarticle.php?id=43&layout=abstract | * Specializing PA bounds: http://www.lmcs-online.org/ojs/viewarticle.php?id=43&layout=abstract | ||