Search

• < Previous
• 1
• Next >

---

Definable decompositions for graphs of bounded linear cliquewidth

Mikołaj Bojańczyk ; Martin Grohe ; Michał Pilipczuk.

We prove that for every positive integer k, there exists an MSO_1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some cliquewidth decomposition of the graph of width bounded by a function of k. A direct corollary of this result is the equivalence of&nbsp;[&hellip;]

---

Randomisation and Derandomisation in Descriptive Complexity Theory

Kord Eickmeyer ; Martin Grohe.

We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic L we introduce a new logic BPL, bounded error probabilistic L, which is defined from L in a similar way as the complexity class BPP, bounded error probabilistic polynomial time, is&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;]

---

Model-Checking Problems as a Basis for Parameterized Intractability

Joerg Flum ; Martin Grohe.

Most parameterized complexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem (the so-called weighted satisfiability problem). For example, Downey and Fellow's W-hierarchy is of this form. But there are also classes, for example, the A-hierarchy, that&nbsp;[&hellip;]

---

The succinctness of first-order logic on linear orders

Martin Grohe ; Nicole Schweikardt.

Succinctness is a natural measure for comparing the strength of different logics. Intuitively, a logic L_1 is more succinct than another logic L_2 if all properties that can be expressed in L_2 can be expressed in L_1 by formulas of (approximately) the same size, but some properties can be expressed&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;]

---