Differences

This shows you the differences between two versions of the page.

--- sav07_lecture_3_skeleton [2007/03/20 14:32]
vkuncak
+++ sav07_lecture_3_skeleton [2007/03/20 14:42]
vkuncak
@@ Line 39: / Line 39: @@
 assume true  = skip   (does nothing)
 ==== Composing formulas using relation composition ====
-This is perhaps the most direct way of transforming programs to formulas.
+This is perhaps the most direct way of transforming programs to formulas.  It creates formulas that are linear in the size of the program.
-It creates formulas that are linear in the size of the program.
 Non-deterministic choice is union of relations, that is, disjunction of formulas:
-CR(c1; c2) = CR(c1) | CR(c2)
+CR(c1 [] c2) = CR(c1) | CR(c2)
+In sequential composition we follow the rule for composition of relations.  We want to get again formula with free variables x_0,y_0,x,y.  So we need to do renaming.  Let x_1,y_1,error_1 be fresh variables.
+CR(c1 ; c2) = exists x_1,y_1,error_1.  CR(c1)[x:=x_1,y:=y_1,error:=error_1] & CR(c2)[x:=x_1,y:=y_1,error:=error_1]
+otherwise
+CR(c)=R(c)     (base case)
+==== Accumulation of equalities ====
+This approach generates many variables and many frame conditions.
+Ignoring error for the moment:
+  R(x=3) = (x=3 & y=y_0)
+  R(y=x+2) = (y=x_0 + 2 & x=x_0)
+  CR(x=3;y=x+2) = x_1=3 & y_1 = y_0 & y = x_1 + 2 & x = x_1
+But if a variable is equal to another, it can be substituted using the substitution rules
+(exists x_1. x_1 = t & F(x_1))     <->    F(t)
+(forall x_1. x_1 = t -> F(x_1)     <->    F(t)
 ==== Papers ====