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:59] vkuncak |
sav07_lecture_13_skeleton [2007/05/02 10:19] 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. Bounding cube length. | + | 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 ==== | ==== Model checking ==== | ||
| Finite state space for now. | Finite state space for now. | ||
| - | |||
| - | BDDs. | ||
| Bounded model checking for finite diameter systems. | Bounded model checking for finite diameter systems. | ||
| + | |||
| + | BDDs. | ||
| ==== Counterexample-driven refinement ==== | ==== Counterexample-driven refinement ==== | ||