Outline for April 8, 2003

  1. General case: It is undecidable whether a given state of a given protection system is safe for a given generic right.
    1. Represent TM as ACM; reduce halting problem to it
  2. Take-Grant
    1. Introduce as counterpoint to HRU result
    2. Show symmetry
    3. Show islands (maximal subject-only tg-connected subgraphs)
    4. Show bridges (as a combination of terminal and initial spans)
    5. 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:
      1. there is a vertex y′ with an edge from y′ to y labeled r;
      2. there is a subject y′′ which terminally spans to y′, or y′′ = y′;
      3. there is a subject x′ which initially spans to x, or x′ = x; and
      4. 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.