41 citations · 68 across the 28 of their papers we have counts for
36 papers
A Rank-Preserving Gaifman Normal Form for First-Order Logic on Weighted Structures
Steffen van Bergerem, Martin Grohe, Charlotte Lenz +1
We prove a rank-preserving version of Gaifman's Theorem. Compared to earlier rank-preserving locality theorems (in particular, [Grohe, Kreutzer, Siebertz, JACM 2017]), our theorem…
Complexity of Clique-Guarded First-Order Logic with Counting
Steffen van Bergerem, Johannes Friedrich Lange, Nicole Schweikardt
We introduce clique-guarded first-order logic with counting (cgFOC), a fragment of the first-order logic with counting FOC [Kuske and Schweikardt, LICS 2017], and we study the comp…
A Rank-Preserving Gaifman Normal Form
Martin Grohe, Nicole Schweikardt
We introduce a rank measure for first-order logic and prove a "rank-preserving'" version of Gaifman's theorem. Compared to earlier "rank-preserving locality theorems'" (in particul…
Structural Indexing of Relational Databases for the Evaluation of Free-Connex Acyclic Conjunctive Queries
Cristian Riveros, Benjamin Scheidt, Nicole Schweikardt
We present an index structure to boost the evaluation of free-connex acyclic conjunctive queries (fc-ACQs) over relational databases. The main ingredient of the index associated wi…
Characterization and Decidability of FC-Definable Regular Languages
Sam M. Thompson, Nicole Schweikardt, Dominik D. Freydenberger
FC is a first-order logic that reasons over all factors of a finite word using concatenation, and can define non-regular languages like that of all squares (ww). In this paper, we…
Learning Aggregate Queries Defined by First-Order Logic with Counting
Steffen van Bergerem, Nicole Schweikardt
In the logical framework introduced by Grohe and Turán (TOCS 2004) for Boolean classification problems, the instances to classify are tuples from a logical structure, and Boolean c…