Search

• < Previous
• 1
• Next >

---

L-Recursion and a new Logic for Logarithmic Space

Martin Grohe ; Berit Grußien ; André Hernich ; Bastian Laubner.

We extend first-order logic with counting by a new operator that allows it to formalise a limited form of recursion which can be evaluated in logarithmic space. The resulting logic LREC has a data complexity in LOGSPACE, and it defines LOGSPACE-complete problems like deterministic reachability and&nbsp;[&hellip;]

---

Infinite Probabilistic Databases

Martin Grohe ; Peter Lindner.

Probabilistic databases (PDBs) model uncertainty in data in a quantitative way. In the established formal framework, probabilistic (relational) databases are finite probability spaces over relational database instances. This finiteness can clash with intuitive query behavior (Ceylan et al., KR&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;]

---