6 papers
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…
Verification of Population Protocols with Unordered Data
Steffen van Bergerem, Roland Guttenberg, Sandra Kiefer +3
Population protocols are a well-studied model of distributed computation in which a group of anonymous finite-state agents communicates via pairwise interactions. Together they dec…
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 mona…
Simulating Logspace-Recursion with Logarithmic Quantifier Depth
Steffen van Bergerem, Martin Grohe, Sandra Kiefer +1
The fixed-point logic LREC= was developed by Grohe et al. (CSL 2011) in the quest for a logic to capture all problems decidable in logarithmic space. It extends FO+C, first-order l…
On the Parameterized Complexity of Learning First-Order Logic
Steffen van Bergerem, Martin Grohe, Martin Ritzert
We analyse the complexity of learning first-order queries in a model-theoretic framework for supervised learning introduced by (Grohe and Turán, TOCS 2004). Previous research on th…
Learning Concepts Described by Weight Aggregation Logic
Steffen van Bergerem, Nicole Schweikardt
We consider weighted structures, which extend ordinary relational structures by assigning weights, i.e. elements from a particular group or ring, to tuples present in the structure…