Assignment 3

Discussion is encouraged, but Plagiarism is NOT. Write your own solutions, without copying from other's (friends, books, webpages etc.).

This assignment has 4 questions.

Consider a semi-lattice (S, ∧), and a partial order ≤: ∀x, y ∈ S, x ≤ y iff x ∧ y = x

Prove that the following two definitions of monotonicity are equivalent for any function f : S → S.

1. ∀x, y ∈ S, x ≤ y ⇒ f(x)≤f(y)
2. ∀x, y ∈ S, f(x ∧ y)≤f(x)∧f(y)

Let f : S → S be a monotonic function on a complete lattice (S, ∨, ∧). Using the concepts covered in class, prove that fix-points of f (i.e. members of fix(f)) form a complete lattice.

An edge in a flow graph is a back edge if its head dominates its tail.

Prove that every back edge is a retreating edge in every DFST of every flow graph.

In a flow graph, the natural loop of a back edge a → b is {b} plus the set of nodes that can reach a without going through b.

Prove that two natural loops are either disjoint, identical, or nested.