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?