Outline for April 11, 2000
1. Greetings and felicitations!
a. Homework
b. Handouts
2. General case: It is undecidable whether a given state of a given protection system is safe for a given generic right.
a. Represent TM as ACM; reduce halting problem to it
3. Take-Grant
a. Introduce as counterpoint to HRU result
b. Show bridges (as a combination of terminal and initial spans)
c. Show islands (maximal subject-only tg-connected subgraphs)
d. can…share(r, x, y, G0) iff there is an edge from x to y labelled r in G0, 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
I1, ..., In connected by bridges for which x' is in I1 and y' is in In .
e. Describe can…steal; don't state theorem
4. Decidability vs. Undecidability
a. Notion of type; subject, object types
b. Attenuation:
c. If attenuating acyclic, it's decidable; so that is sufficient. Open question: is it necessary?