27 citations · 79 across the 13 of their papers we have counts for
23 papers
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 i…
Ehrenfeucht-Fraïssé Games in Semiring Semantics
Sophie Brinke, Erich Grädel, Lovro Mrkonjić
Ehrenfeucht-Fraïssé games provide a fundamental method for proving elementary equivalence (and equivalence up to a certain quantifier rank) of relational structures. We investigate…
Locality Theorems in Semiring Semantics
Clotilde Bizière, Erich Grädel, Matthias Naaf
Semiring semantics of first-order logic generalises classical Boolean semantics by permitting truth values from a commutative semiring, which can model information such as costs or…
Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics
Erich Grädel, Hayyan Helal, Matthias Naaf +1
Semiring semantics evaluates logical statements by values in some commutative semiring K. Random semiring interpretations, induced by a probability distribution on K, generalise ra…
Semiring Provenance for Büchi Games: Strategy Analysis with Absorptive Polynomials
Erich Grädel, Niels Lücking, Matthias Naaf
This paper presents a case study for the application of semiring semantics for fixed-point formulae to the analysis of strategies in Büchi games. Semiring semantics generalizes the…
Limitations of the Invertible-Map Equivalences
Anuj Dawar, Erich Grädel, Moritz Lichter
This note draws conclusions that arise by combining two recent papers, by Anuj Dawar, Erich Grädel, and Wied Pakusa, published at ICALP 2019 and by Moritz Lichter, published at LIC…