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_12_skeleton [2007/04/26 12:58] vkuncak |
sav07_lecture_12_skeleton [2007/04/26 13:12] vkuncak |
||
|---|---|---|---|
| Line 7: | Line 7: | ||
| * formulate standard condition for inductive invariant over templates | * formulate standard condition for inductive invariant over templates | ||
| * eliminate implication using Farkas lemma | * eliminate implication using Farkas lemma | ||
| - | * remove existential [[http://en.wikipedia.org/wiki/Real_closed_field#Decidability_and_quantifier_elimination|quantifiers using quantifier elimination for real fields]] | + | * remove existential quantifiers using [[http://en.wikipedia.org/wiki/Real_closed_field#Decidability_and_quantifier_elimination|quantifier elimination for real fields]] |
| Quantifier elimination does not scale in general. Some improvements: | Quantifier elimination does not scale in general. Some improvements: | ||
| Line 15: | Line 15: | ||
| * factorization: transforms parameterized linear condition into a product, which becomes disjunction | * factorization: transforms parameterized linear condition into a product, which becomes disjunction | ||
| * additional lemmas | * additional lemmas | ||
| + | |||
| ===== Counterexample-driven analysis ===== | ===== Counterexample-driven analysis ===== | ||
| - | * [[http://research.microsoft.com/~leino/papers/krml155.pdf|Loop invariants on demand]] | + | * Paper: [[http://research.microsoft.com/~leino/papers/krml155.pdf|Loop invariants on demand]] |
| - | * [[http://research.microsoft.com/copyright/accept.asp?path=http://research.microsoft.com/~sriram/Papers/tacas2006.pdf&pub=15%22|Counterexample Driven Refinement for Abstract Interpretation]] | + | |
| + | ==== Loop invariants in demand ==== | ||
| + | |||
| + | * Paper: [[http://research.microsoft.com/copyright/accept.asp?path=http://research.microsoft.com/~sriram/Papers/tacas2006.pdf&pub=15%22|Counterexample Driven Refinement for Abstract Interpretation]] | ||
| + | |||
| + | Key points: | ||
| + | * abstract interepretation | ||
| + | * automated refinement of domain: compare to ASTREE (also some parameters, e.g. packing) | ||
| + | |||
| + | ==== Predicate abstraction ==== | ||
| * [[Predicate abstraction]] | * [[Predicate abstraction]] | ||