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_18 [2007/05/28 22:41] vasu.singh |
sav07_lecture_18 [2007/05/29 00:43] vasu.singh |
||
---|---|---|---|
Line 27: | Line 27: | ||
This suggests that the two programs above are not equivalent for the purpose of reasoning | This suggests that the two programs above are not equivalent for the purpose of reasoning | ||
in concurrently executing programs. | in concurrently executing programs. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
Line 67: | Line 72: | ||
An example | An example | ||
+ | |||
+ | { b = x + y } | ||
+ | while (*) do | ||
+ | if (*) then | ||
+ | x++; | ||
+ | y--; | ||
+ | else | ||
+ | y++; | ||
+ | x--; | ||
+ | endif | ||
+ | end | ||
+ | || | ||
+ | while (*) do | ||
+ | if (*) then | ||
+ | atomic{ | ||
+ | x++; | ||
+ | y--; | ||
+ | } | ||
+ | else | ||
+ | atomic{ | ||
+ | y++; | ||
+ | x--; | ||
+ | } | ||
+ | endif | ||
+ | end | ||
+ | { b = x + y } | ||
+ | |||
+ | In our language, this example can be expressed as | ||
+ | | ||
+ | (atomic(x:=x+1;y:=y-1)[]atomic(x:=x-1;y:=y+1))* || (atomic(x:=x+1;y:=y-1)[]atomic(x:=x-1;y:=y+1))* | ||
+ | |||
+ | $ = (r1[]r2)^*||(r3[]r4)^* \subseteq (r1 [] r2 [] r3 [] r4)^*$ | ||
==== Global reachability invariants ==== | ==== Global reachability invariants ==== |