On the Parameterized Complexity of Learning First-Order Logic

ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), vol. 17, pp. 337–346

Abstract

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 the complexity of learning in this framework focussed on the question of when learning is possible in time sublinear in the background structure.

Authors 3

1. Steffen van Bergerem Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

2. Martin Grohe Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

3. Martin Ritzert

   Aarhus University

   Affiliation as printed

   Aarhus University, Aarhus, Denmark