- Greetings and felicitations!
- Homework
- Handouts

- 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

- Take-Grant
- 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**,*G*_{0}) iff there is an edge from**x**to**y**labelled*r*in*G*_{0}, 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
*I*_{1}, ...,*I*connected by bridges for which_{n}**x'**is in*I*_{1}and**y'**is in*I*._{n}

- there is a vertex
- Describe can·steal; don't state theorem

- Decidability vs. Undecidability
- Notion of type; subject, object types
- Attenuation
- If attenuating acyclic, it's decidable; so that is sufficient. Open question: is it necessary?

Send email to bishop@cs.ucdavis.edu.

Department of Computer Science

University of California at Davis

Davis, CA 95616-8562