3 papers
cs.LO2026
Preservation Theorems in Semiring Semantics
Sophie Brinke, Anuj Dawar, Erich Grädel +1
We study the status of preservation theorems such as the ÅoÅ-Tarski theorem and the homomorphism preservation theorem in the context of semiring semantics. Semiring semantics has…
cs.LO2025
Symmetric Proofs in the Ideal Proof System
Anuj Dawar, Erich Grädel, Leon Kullmann +1
We consider the Ideal Proof System (IPS) introduced by Grochow and Pitassi and pose the question of which tautologies admit symmetric proofs, and of what complexity. The symmetry r…
cs.LO2024
Provenance Analysis and Semiring Semantics for First-Order Logic
Erich Grädel, Val Tannen
A provenance analysis for a query evaluation or a model checking computation extracts information on how its result depends on the atomic facts of the model or database. Traditiona…