Extra Credit #A

Due: January 19, 2024
Points: 100

Prove or give a counterexample:
The predicate can•share(α, x, y, G₀) is true if and only if there is an edge from x to y in G₀ 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′ initially spans to s.
4. There is a sequence of subjects x₁, …, x_n with x₁ = x′, x_n = s′, and x_i and x_i+1 (1 ≤ i < n) being connected by an edge labeled t, an edge labeled g, or a bridge.

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: mabishop@ucdavis.edu

ECS 235B, Foundations of Computer and Information Security Version of January 5, 2024 at 8:37PM

You can also obtain a PDF version of this.