The parameterized complexity of learning monadic second-order logic

DOI10.4230/LIPICS.CSL.2025.8MaRDI QIDQ7261414zbMATH OpenFDO

Authors Steffen van Bergerem, Martin Grohe, Nina Runde

Publication date 9 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CSL.2025.8

zbMATH Keywords

supervised learningclique-widthmonadic second-order logicparameterized complexityfixed-parameter tractableagnostic probably approximately correct learningBoolean classificationmonadic second-order definable concept learning

Mathematics Subject Classification ID

Logic in computer science (03B70)

Cites work

• scientific article; zbMATH DE number 2080453 (Why is no real title available?)
• scientific article; zbMATH DE number 6999908 (Why is no real title available?)
• scientific article; zbMATH DE number 795584 (Why is no real title available?)
• scientific article; zbMATH DE number 7561484 (Why is no real title available?)
• A combinatorial problem; stability and order for models and theories in infinitary languages
• A theory of the learnable
• Approximating clique-width and branch-width
• Complexity theoretic hardness results for query learning
• Conjunctive queries: unique characterizations and exact learnability
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Foundations of machine learning
• ICE-based refinement type discovery for higher-order functional programs
• Inductive Logic Programming: Theory and methods
• Inductive logic programming
• Learnability and definability in trees and similar structures
• Learnability and the Vapnik-Chervonenkis dimension
• Learning Boolean functions with queries
• Learning concepts definable in first-order logic with counting
• Learning concepts described by weight aggregation logic
• Learning first-order definable concepts over structures of small degree
• Learning join queries from user examples
• Learning schema mappings
• Linear time solvable optimization problems on graphs of bounded clique-width
• Multi-clique-width
• On the Relationship Between Clique-Width and Treewidth
• On the density of families of sets
• Parameterized Learnability of k-Juntas and Related Problems
• Parametrized complexity theory.
• Regularizing conjunctive features for classification
• Schema mapping discovery from data instances
• The complexity of reverse engineering problems for conjunctive queries
• Understanding machine learning. From theory to algorithms
• Upper bounds to the clique width of graphs

This page was built for publication: The parameterized complexity of learning monadic second-order logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7261414)