Rate-Distortion for Reversible Causal Nets under Closure-Preserving Fidelity
2026-06-15 • Information Theory
Information Theory
AI summaryⓘ
The authors develop a way to measure how much you can simplify a record of events (a log) without losing important information needed to reverse actions. They use a mathematical concept called a semantic closure to capture what really matters in the log and define a measure of how changes to one fact affect the overall meaning. By separating the log into essential core facts and redundant extras, they show that only the core matters when compressing the log for perfect reversibility. They test their theory using models of reversible computations and confirm their predictions with calculations.
rate-distortion theoryreversible loggingsemantic closureDatalogrollbackconfusability hypergraphevent structurescausal netsinformation theory
Authors
Jianfeng Xu
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.