# Outline for April 8, 2003

- General case: It is undecidable whether a given state of a given
protection system is safe for a given generic right.
- Represent TM as ACM; reduce halting problem to it

- Take-Grant
- Introduce as counterpoint to HRU result
- Show symmetry
- Show islands (maximal subject-only tg-connected subgraphs)
- Show bridges (as a combination of terminal and initial spans)
- can·share(
*r*, **x**, **y**, *G*_{0})
iff there is an edge from **x** to **y** labeled *r* in
*G*_{0}, or all of the following hold:
- there is a vertex
**y**′ with an edge from
**y**′ to **y** labeled *r*;
- there is a subject
**y**′′ which
terminally spans to **y**′, or
**y**′′ = **y**′;
- there is a subject
**x**′ which initially spans
to **x**, or **x**′ = **x**; and
- there is a sequence of islands
*I*_{1}, ...,
*I*_{n} connected by bridges for which
**x**′ is in *I*_{1}
and **y**′ is in *I*_{n}.

This is available in Postscript and PDF.