Search

• < Previous
• 1
• Next >

---

Definability of linear equation systems over groups and rings

Anuj Dawar ; Eryk Kopczynski ; Bjarki Holm ; Erich Grädel ; Wied Pakusa.

Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the solvability of linear equation systems over finite groups and rings from the viewpoint of logical (inter-)definability.&nbsp;[&hellip;]

---

A Finite-Model-Theoretic View on Propositional Proof Complexity

Erich Grädel ; Martin Grohe ; Benedikt Pago ; Wied Pakusa.

We establish new, and surprisingly tight, connections between propositional proof complexity and finite model theory. Specifically, we show that the power of several propositional proof systems, such as Horn resolution, bounded-width resolution, and the monomial calculus of bounded degree, can be&nbsp;[&hellip;]

---

Semiring Provenance for B\"uchi 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\"uchi games. Semiring semantics generalizes the classical Boolean semantics by permitting multiple truth values from certain semirings. Evaluating the fixed-point&nbsp;[&hellip;]

---