Differences

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

--- sav08:review_of_fixpoints_in_semantics [2008/04/30 10:43]
vkuncak
+++ sav08:review_of_fixpoints_in_semantics [2008/04/30 10:54]
vkuncak
@@ Line 1: / Line 1: @@
 ====== Review of Fixpoints in Semantics ======
-**Definition:** Given a set $A$ and a function $f : A \to A$ we say that $x \in A$ is a fixed point (fixpoint) of $f$ if $f(x)=x$.
-**Definition:** Let $(A,\le)$ be a partial order, let $f : A \to A$ be a monotonic function on $(A,\le)$, and let the set of its fixpoints be $S = \{ x \mid f(x)=x \}$.  If the least element of $S$ exists, it is called the **least fixpoint**, if the greatest element of $S$ exists, it is called the **greatest fixpoint**.
-Note:
-  * a function can have various number of fixpoints. Take $f : {\cal Z} \to {\cal Z}$,
-     * $f(x)=x$ the set of fixedpoints is
-     * $f(x)=x^2$ the set of fixedpoints is
-     * $f(x)=3x-6$ has exactly one fixpoint
-  * a function can have at most one least and at most one greatest fixpoint
-We can use fixpoints to give meaning to recursive and iterative definitions
-  * key to describing arbitrary long executions in programs
 ===== Transitive Closure as Least Fixedpoint =====
@@ Line 84: / Line 70: @@
 Let $p_0$ be initial program counter and $I$ the set of values of program variables in $p_0$.
-The set of reachable states is defined as the least solution of:
+The set of reachable states is defined as the least solution of constraints:
+\[
+\begin{array}{l}
+  I \subseteq C(p_0) \\
+  \bigwedge_{(p_1,p_2) \in E} sp(C(p),r(c(p_1,p_2)))) \subseteq C(p_2)
+\end{array}
+\]
+where $c(p_1,p_2)$ is command associated with edge $(p_1,p_2)$, $r(c(p_1,p_2))$ is relation for this command.