Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | Next revision Both sides next revision | ||
sav07_lecture_3_skeleton [2007/03/20 14:32] vkuncak |
sav07_lecture_3_skeleton [2007/03/20 14:35] vkuncak |
||
---|---|---|---|
Line 39: | Line 39: | ||
assume true = skip (does nothing) | assume true = skip (does nothing) | ||
+ | |||
==== Composing formulas using relation composition ==== | ==== 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: | 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] | ||
==== Papers ==== | ==== Papers ==== |