3 results
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 […]
Published on January 25, 2021
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 […]
Published on February 25, 2022
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 […]
Published on June 14, 2022