Outline for April 11, 2000
- Greetings and felicitations!
- 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 bridges (as a combination of terminal and initial spans)
- Show islands (maximal subject-only tg-connected subgraphs)
- 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:
- there is a vertex y'' with an edge from y' to
y labelled 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.
- Describe can·steal; don't state theorem
- Decidability vs. Undecidability
- Notion of type; subject, object types
- If attenuating acyclic, it's decidable; so that is sufficient. Open question: is it necessary?
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 4/12/2000