Extra Credit #A Revision 1

Due: January 19, 2024
Points: 100

Revision 1, January 23, 2024: (1) The extra credit is worth 30 points, not 100. (2) In the HTML page, part (c) should say “terminal”, not “initial”. The PDF is correct.

Prove or give a counterexample:
The predicate can•share(α, x, y, G0) is true if and only if there is an edge from x to y in G0 labeled α, or if the following hold simultaneously.

  1. There is a vertex s with an s-to-y edge labeled α.
  2. There is a subject vertex x′ such that x′ = x or x′ initially spans to x.
  3. There is a subject vertex s′ such that s′ = s or s′ terminally spans to s.
  4. There is a sequence of subjects x1, …, xn with x1 = x′, xn = s′, and xi and xi+1 (1 ≤ i < n) being connected by an edge labeled t, an edge labeled g, or a bridge.
UC Davis sigil
Matt Bishop
Office: 2209 Watershed Sciences
Phone: +1 (530) 752-8060
Email: [email protected]
ECS 235B, Foundations of Computer and Information Security
Version of January 23, 2024 at 11:47AM

 You can also obtain a PDF version of this.

Valid HTML 4.01 Transitional Built with BBEdit Built on a Macintosh