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…