Showing 2023Show all
2 papers · 1 filter
cs.LO2023
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…
cs.LO2023
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…