4 papers
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…
Learning Concepts Definable in First-Order Logic with Counting
Steffen van Bergerem
We study Boolean classification problems over relational background structures in the logical framework introduced by Grohe and Turán (TOCS 2004). It is known (Grohe and Ritzert,…
The Parameterized Complexity of Learning Monadic Second-Order Logic
Steffen van Bergerem, Martin Grohe, Nina Runde
Within the model-theoretic framework for supervised learning introduced by Grohe and Turán (TOCS 2004), we study the parameterized complexity of learning concepts definable in mon…
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…