CS618 Program Analysis (2016-17 Ist Semester, IIT Bombay)

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.

  1. Monotonic Functions
  2. Knaster-Tarski Fixed Point Theorem
  3. Back Edges in a Flow Graph
  4. Natural Loops in a Flow Graph

Q1: Monotonic Functions

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)

Q2: Knaster‐Tarski Fixed Point Theorem

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.

Q3: Back Edges in a Flow Graph

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.

Q4: Natural Loops in a 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.


Take me to the Top

powered by Pandoc

Last Modified at : Wed Aug 9 06:56:17 IST 2017