Outline for April 11, 2000

1. Greetings and felicitations!
   1. Homework
   2. Handouts
2. 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
3. Take-Grant
   1. Introduce as counterpoint to HRU result
   2. Show bridges (as a combination of terminal and initial spans)
   3. Show islands (maximal subject-only tg-connected subgraphs)
   4. can·share(r, x, y, G₀) iff there is an edge from x to y labelled r in G₀, or all of the following hold:
      1. there is a vertex y'' with an edge from y' to y labelled 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 I₁, ..., I_n connected by bridges for which x' is in I₁ and y' is in I_n.
   5. Describe can·steal; don't state theorem
4. Decidability vs. Undecidability
   1. Notion of type; subject, object types
   2. Attenuation
   3. If attenuating acyclic, it's decidable; so that is sufficient. Open question: is it necessary?