SB CSE 675
Fall 2000
Program Transformation and Program Analysis
Annie Liu
Solution 9
Handout S9
Dec. 6, 2000

Problem 1.

  f(x) = if #{b:[a,b] in f|a=x}=1 then arb{b:[a,b] in f|a=x} else om endif
       = if exists [a,b] in f| a=x and not exists [a,c] in f| b!=c then b
         else om endif

  f{x} = {y: [u,y] in f| u = x}	not = {y: [x,y] in f}
       = {y in range f| [x,y] in f}

  f[s] = + / {f{x}: x in s}		where one could copy f{x} above in here
       = {y: [x,y] in f| x in s}
       = {y: x in s, y in f{x}}

Problem 2.

  program cycle;
    read(e);

    s := domain e + range e;	-- only domain e is necessary
    while exists x in s| e{x} * s = {} loop
      s less := x;	-- repeatedly remove elem whose successors are not in s
    end loop;

    print(s);		-- graph e contains a cycle iff s /= {}
  end;

Problem 3. change e[s]-s to w + e[s] - s

Bonus Problem.

  4.1 */{s in pow({x}+range e)|x in s and +/{+/neighbors(x,e)|x in s} subset s}
  4.2 isconn(s) = forall x in nodes(s)| reach(x) = s
  4.3 ispath(s) = isconn(s) and (#leaves(s)=2 and
		forall x in (nodes(s) - leaves(s))| #neighbors(x,s) = 2)
  4.4 paths(x) = {s in pow(e)| ispath(s) and x in leaves(s)}

  4. maxpaths(x) = {s in paths(x)| #s = max/{#q: q in paths(x)}}
  5. furthest(x) = {y: s in maxpaths(x), y in leaves(s)| y /= x}
  6. middle(s) = {x in nodes(s)| #(arb maxpaths(x)) = #s/2 + #s mod 2}

  tree center: middle(arb maxpaths(arb furthest(arb nodes(e)))

  this is in very-high-level SETL.