Outline for January 21, 1999

  1. Greetings and felicitations!
    1. Please get your project proposals in as soon as possible, so you can get started
    2. Hand out new homework; point out #6 and review rules of attacking lassen over the network
  2. Take-Grant
    1. Show bridges (as a combination of terminal and initial spans)
    2. Show islands (maximal subject-only tg-connected subgraphs)
    3. 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 .
    4. Describe can*steal; don't state theorem
  3. Decidability vs. Undecidability
    1. Notion of type; subject, object types
    2. SPM: types fixed at creation
    3. tickets: X/r (apply right r to entity X), X/r:c (c copy flag, so can give right away)
    4. link predicate: X possesses tickets in set dom(X). Then link(X, Y) = rights over X and Y dom(X) and dom(Y), and true; basically, everything connecting X and Y
    5. copying X/r:c from dom(X) to dom(Z): needs X/rc dom(X), link(X, Z), and [[tau]](X)/r:c f([[tau]](X), [[tau]](Z)), f filter function
    6. Do TG example pp. 82-83
    7. create: can-create (cc) relation says that subject of type a can create entities of type b iff cc(a, b) holds
    8. create rule: crp(a, b) = set of tickets added to dom(A), crc(a, b) = set of tickets added to dom(B)
    9. attenuation: cr(a, b) = crpp(a,b)|crc(a, b) is attenuating if: (1) crc(a, b) SUBSETEQ crp(a, b) and (2) a/r:c SUBSETEQ crp(a, b) self/r:c crp(a, b)
    10. cyclic: cc(a, b) cc(b, a)
    11. if attenuating acyclic, it's decidable; so that is sufficient. Open question: is it necessary?

You can get this document in ASCII text, Framemaker+SGML version 5.5, PDF (for Acrobat 3.0 or later), or Postscript.
Send email to cs253@csif.cs.ucdavis.edu.

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562

Page last modified on 3/19/99