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_4 [2007/03/27 16:28] leander.eyer |
sav07_lecture_4 [2007/03/27 16:46] leander.eyer |
||
|---|---|---|---|
| Line 139: | Line 139: | ||
| and is represented by the function a[0->3][1->2][2->1]. Therefore, the last value of the array is expressed as a[0->3][1->2][2->1](2) = 1. | and is represented by the function a[0->3][1->2][2->1]. Therefore, the last value of the array is expressed as a[0->3][1->2][2->1](2) = 1. | ||
| + | |||
| Line 168: | Line 169: | ||
| ===Avoiding exponential explosion using flattening=== | ===Avoiding exponential explosion using flattening=== | ||
| - | Desugaring if-then-else expressions introduces a disjunction of two conjunction. If conditional expressions are embedded, the number of conjunction and conjunctions will explode. | + | Desugaring if-then-else expressions introduces a disjunction of two conjunctions. If conditional expressions are embedded, the number of conjunctions and disjunctions will explode. |
| To avoid this explosion of terms, one may introduce additional //variables//. For instance, the expression: | To avoid this explosion of terms, one may introduce additional //variables//. For instance, the expression: | ||
| Line 176: | Line 177: | ||
| can be flattened as | can be flattened as | ||
| - | y<sub>1</sub> = y + 5 | + | y<sub>1</sub> = y + 5\\ |
| - | ∧ y<sub>2</sub> = 3y<sub>1</sub> | + | ∧ y<sub>2</sub> = 3y<sub>1</sub>\\ |
| - | ∧ x < y<sub>2</sub> | + | ∧ x < y<sub>2</sub>\\ |
| - | This gives a new grammar for //atomic formula//: | + | This gives a new grammar for //atomic formulas//: |
| A := R(v,...,v) | v = f(v,...,v) | v = c | A := R(v,...,v) | v = f(v,...,v) | v = c | ||
| Line 191: | Line 192: | ||
| a = a [t<sub>1</sub>->t<sub>2</sub>]; | a = a [t<sub>1</sub>->t<sub>2</sub>]; | ||
| - | The value of K is know for //global arrays// (statically defined). The case of dynamically allocated arrays (like the one in Java) will be dealt in a following section. | + | The value of K is known for //global arrays// (statically defined). The case of dynamically allocated arrays (like the one in Java) will be dealt in a further section. |
| Line 216: | Line 218: | ||
| Possible mathematical model: fields as functions from objects to objects. | Possible mathematical model: fields as functions from objects to objects. | ||
| - | left : Node => Node | + | left : Node -> Node |
| - | right : Node => Node | + | right : Node -> Node |
| What is the meaning of assignment? | What is the meaning of assignment? | ||
| Line 268: | Line 270: | ||
| assume(x ∉ alloc); | assume(x ∉ alloc); | ||
| alloc = alloc ∪ {x} | alloc = alloc ∪ {x} | ||
| + | |||
| Line 273: | Line 276: | ||
| ==== Dynamically allocated arrays ==== | ==== Dynamically allocated arrays ==== | ||
| - | When we allow dynamically allocated arrays, we introduce an additional parameter to the array function which identifies the array in question. | + | When we allow dynamically allocated arrays, we introduce a new global function **array** which maps a pair (arrayID, index) to values. |
| x[i] = v; | x[i] = v; | ||
| Line 286: | Line 289: | ||
| ===== Proving formulas with uninterpreted functions ===== | ===== Proving formulas with uninterpreted functions ===== | ||
| + | |||
| Line 300: | Line 304: | ||
| The congruence closure algorithm can be used to proove the correctness of quantifier free formulas by examining congruence closures of the statements in the formula. | The congruence closure algorithm can be used to proove the correctness of quantifier free formulas by examining congruence closures of the statements in the formula. | ||
| - | Recall the following properties of relations: | + | Recall the following properties of the relation **equivalence**: |
| - x = x (everything is equal to itself) | - x = x (everything is equal to itself) | ||
| - x = y -> y = x (reflexivity) | - x = y -> y = x (reflexivity) | ||
| - x = y ∧ y = z -> x = z (transitivity) | - x = y ∧ y = z -> x = z (transitivity) | ||
| - | - (x1 = x2 ∧ y1 = y2) -> f(x1, y1) = f(x2, y2) (equivalence in functions) | + | |
| + | A congruence is an equivalence relationship with the additional property | ||
| + | * (x1 = x2 ∧ y1 = y2) -> f(x1, y1) = f(x2, y2) | ||
| + | |||
| + | a ≡ b (mod n) is a congruence in respect to addition. Indeed: | ||
| + | |||
| + | a ≡ b (mod n) ∧ c ≡ d (mod n) -> a + c ≡ b + d (mod n) | ||
| Equality is a congruence with respect to all function symbols. | Equality is a congruence with respect to all function symbols. | ||