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
- 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, G0)
iff there is an edge from x to y labeled r in
G0, 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 I1, ...,
In connected by bridges for which
x′ is in I1
and y′ is in In.
This is available in Postscript and PDF.