[2603.26725] Capability Safety as Datalog: A Foundational Equivalence

Computer Science > Logic in Computer Science arXiv:2603.26725 (cs) [Submitted on 20 Mar 2026] Title:Capability Safety as Datalog: A Foundational Equivalence Authors:Cosimo Spera View a PDF of the paper titled Capability Safety as Datalog: A Foundational Equivalence, by Cosimo Spera View PDF HTML (experimental) Abstract:We prove that capability safety admits an exact representation as propositional Datalog evaluation (Datalogprop: the monadic, ground, function-free fragment of first-order logic), enabling the transfer of algorithmic and structural results unavailable in the native formulation. This addresses two structural limitations of the capability hypergraph framework of Spera [2026]: the absence of efficient incremental maintenance, and the absence of a decision procedure for audit surface containment. The equivalence is tight: capability hypergraphs correspond to exactly this fragment, no more. Subjects: Logic in Computer Science (cs.LO); Artificial Intelligence (cs.AI) Cite as: arXiv:2603.26725 [cs.LO]   (or arXiv:2603.26725v1 [cs.LO] for this version)   https://doi.org/10.48550/arXiv.2603.26725 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Cosimo Spera [view email] [v1] Fri, 20 Mar 2026 03:28:14 UTC (27 KB) Full-text links: Access Paper: View a PDF of the paper titled Capability Safety as Datalog: A Foundational Equivalence, by Cosimo SperaView PDFHTML (experimental)TeX Source view license Current browse context: cs.LO < prev   |   next...