2026-07-23T18:55:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22765 2025-10-02T11:31:24Z ddc:004 open_access

The Parameterized Complexity of Learning Monadic Second-Order Logic van Bergerem, Steffen Grohe, Martin Runde, Nina monadic second-order definable concept learning agnostic probably approximately correct learning parameterized complexity clique-width fixed-parameter tractable Boolean classification supervised learning monadic second-order logic 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 monadic second-order logic (MSO). We show that the problem of learning an MSO-definable concept from a training sequence of labeled examples is fixed-parameter tractable on graphs of bounded clique-width, and that it is hard for the parameterized complexity class para-NP on general graphs. It turns out that an important distinction to be made is between 1-dimensional and higher-dimensional concepts, where the instances of a k-dimensional concept are k-tuples of vertices of a graph. For the higher-dimensional case, we give a learning algorithm that is fixed-parameter tractable in the size of the graph, but not in the size of the training sequence, and we give a hardness result showing that this is optimal. By comparison, in the 1-dimensional case, we obtain an algorithm that is fixed-parameter tractable in both. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Steffen van Bergerem and Martin Grohe and Nina Runde 2025 Is Part Of LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2025.8 urn:nbn:de:0030-drops-227651 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.8 eng https://creativecommons.org/licenses/by/4.0/legalcode