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_13_skeleton [2007/05/02 09:57] vkuncak |
sav07_lecture_13_skeleton [2007/05/02 10:20] vkuncak |
||
---|---|---|---|
Line 7: | Line 7: | ||
* model checking (finite state or pushdown system) | * model checking (finite state or pushdown system) | ||
* counterexample-driven refinement | * counterexample-driven refinement | ||
+ | |||
==== Abstraction ==== | ==== Abstraction ==== | ||
Line 17: | Line 18: | ||
* best transformer in abstract domain | * best transformer in abstract domain | ||
+ | Computation using wp. Boolean programs. | ||
+ | |||
+ | Precision-preserving optimizations: | ||
+ | * cubes in increasing order | ||
+ | * do not update variables if command cannot change them | ||
+ | * cone of influence to reduce the number of predicates to consider | ||
+ | * syntactic construction of predicates | ||
+ | * caching of calls to theorem prover | ||
+ | Further approximations: | ||
+ | * bounding cube length to 3 | ||
+ | * distributing approximation through logical operations | ||
+ | |||
+ | ==== Model checking ==== | ||
+ | |||
+ | Finite state space for now. | ||
+ | |||
+ | Bounded model checking for finite diameter systems. | ||
+ | |||
+ | BDDs: http://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.pdf | ||
+ | |||
+ | ==== Counterexample-driven refinement ==== | ||
+ | |||
+ | Heuristic refinement | ||
+ | * expressions in branches | ||
+ | * adding weakest preconditions | ||
+ | * Craig's interpolation | ||