4 citations · 4 across the 1 of their papers we have counts for
5 papers
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…
Computing Least and Greatest Fixed Points in Absorptive Semirings
Matthias Naaf
We present two methods to algorithmically compute both least and greatest solutions of polynomial equation systems over absorptive semirings (with certain completeness and continui…
Inferring Lower Runtime Bounds for Integer Programs
Florian Frohn, Matthias Naaf, Marc Brockschmidt +1
We present a technique to infer lower bounds on the worst-case runtime complexity of integer programs, where in contrast to earlier work, our approach is not restricted to tail-rec…
Generalized Absorptive Polynomials and Provenance Semantics for Fixed-Point Logic
Katrin M. Dannert, Erich Grädel, Matthias Naaf +1
Semiring provenance is a successful approach to provide detailed information on the combinations of atomic facts that are responsible for the result of a query. In particular, inte…