Abstract:We develop a semantic rate-distortion theory for reversible logging under a closure-preserving fidelity criterion. An execution history is modeled as a finite set of logged facts, and rollback-relevant meaning is captured by a monotone semantic closure induced by an effective rule system such as Datalog. We introduce a bounded distortion that edits one logged fact and measures the resulting change in closure. A canonical deletion scan decomposes the log into an irredundant core and a redundant remainder; under admissible reconstructions, redundant facts become information-theoretically invisible, yielding a core-only rate-distortion reduction. At perfect fidelity, overlaps among zero-distortion reconstructions induce a confusability hypergraph that determines the minimum rate. We instantiate the framework on reversible causal nets and reversible prime event structures under multiple reversing disciplines, and validate the predictions numerically.
From: Jianfeng Xu [view email]
[v1]
Mon, 15 Jun 2026 11:41:01 UTC (43 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。