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 | ||
|
sav08:mapping_fixpoints_under_lattice_morphisms [2008/05/07 10:31] vkuncak |
sav08:mapping_fixpoints_under_lattice_morphisms [2009/03/26 13:53] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Mapping Fixpoints Under Lattice Morphisms ====== | ====== Mapping Fixpoints Under Lattice Morphisms ====== | ||
| + | |||
| + | **Definition:** Let $(X,\le)$ and $(Y,\sqsubseteq)$ be complete [[lattices]]. We call $F : X \to Y$ a **complete join-morphism** iff for each set $X_1 \subseteq X$ we have | ||
| + | \[ | ||
| + | F(\sqcup X_1) = \sqcup \{ F(a).\ a \in X_1 \} | ||
| + | \] | ||
| **Lemma:** Let $(X,\le)$ and $(Y,\sqsubseteq)$ be complete lattices, and $F : X \to X$, $\Gamma : X \to Y$, $F^\# : Y \to Y$ be complete morphisms (they distribute through arbitrary least upper bound) such that | **Lemma:** Let $(X,\le)$ and $(Y,\sqsubseteq)$ be complete lattices, and $F : X \to X$, $\Gamma : X \to Y$, $F^\# : Y \to Y$ be complete morphisms (they distribute through arbitrary least upper bound) such that | ||
| Line 12: | Line 17: | ||
| In other words, we can approximate $lfp(F)$ by computing $lfp(F^\#)$. | In other words, we can approximate $lfp(F)$ by computing $lfp(F^\#)$. | ||
| - | **Definition:** Height of the lattice is the size of the longest strictly increasing sequence of elements $a_1 \sqsubset a_2 \sqsubset a_3 \ldots$. | ||
| - | Lattice has finite height iff there exists no infinite strictly increasing sequence of elements in the lattice. | ||
| - | |||
| - | Observation: it is decidable to find least fixpoint of morphism $F^{\#}$ in a lattice with finite height. | ||
| - | |||
| - | Lattices with finite height | ||
| - | * finite lattice | ||
| - | * constant propagation lattice | ||