Research proof index

Converse of log_entry_in_cache_and_mono: when running loggingOracle inside cachingOracle, every cache entry that was not in the initial cache has a corresponding log entry. Combined with log_entry_in_cache_and_mono, this shows that (starting from ∅) the cache entries and log entries have the same set of (input, output) pairs. Proof by stru...

When running loggingOracle inside cachingOracle, every log entry ends up in the cache. We prove two properties simultaneously by induction: 1. Every log entry is in the final cache. 2. The initial cache is a subset of the final cache (monotonicity). The proof works by induction on oa. The pure case is trivial (empty log). For query t >>= mx: the...