SB CSE 675Fall 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;

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.
```