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:chaotic_iteration_in_abstract_interpretation [2008/05/20 13:08] vkuncak |
sav08:chaotic_iteration_in_abstract_interpretation [2008/05/20 13:18] vkuncak |
||
---|---|---|---|
Line 30: | Line 30: | ||
\begin{array}{ll} | \begin{array}{ll} | ||
g^{k+1}_i = H_i(g^k_1,\ldots,g^k_n) \\ | g^{k+1}_i = H_i(g^k_1,\ldots,g^k_n) \\ | ||
- | g^{k+1}_j = g^k_j, \mbox{ for } j \neq i & \mbox{\bf chaotic iteration} | + | & \mbox{\bf chaotic iteration} \\ |
+ | g^{k+1}_j = g^k_j, \mbox{ for } j \neq i | ||
\end{array} | \end{array} | ||
\] | \] | ||
Line 66: | Line 67: | ||
Algorithm terminates when worklist is empty (no more changes) | Algorithm terminates when worklist is empty (no more changes) | ||
- | Iteration strategies: | + | Useful iteration strategy: reverse postorder and strongly connected components |
- | * LIFO, FIFO, | + | |
- | * reverse postorder | + | Reverse postorder: follow changes through successors in the graph |
- | * round robin | + | |
- | * strongly connected components | + | Strongly connected component (SCC) of a directed graph: path between each two nodes of component. |
+ | * compute until fixpoint within each SCC | ||
===== References ===== | ===== References ===== |