On the non-efficient PAC learnability of conjunctive queries

DOI10.1016/j.ipl.2023.106431zbMath1529.68127arXiv2208.10255MaRDI QIDQ6072217

Balder ten Cate, Carsten Lutz, Jean Christoph Jung, Maurice Funk

Publication date: 12 October 2023

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2208.10255

zbMATH Keywords

computational learning theoryinductive logic programmingdatabasesconjunctive queries

Mathematics Subject Classification ID

Computational learning theory (68Q32) Database theory (68P15) Logic programming (68N17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equivalence of models for polynomial learnability
• Foundations of inductive logic programming
• Learnability of quantified formulas.
• Learning closed Horn expressions
• A dichotomy theorem for learning quantified Boolean formulas
• Queries and concept learning
• Prediction-hardness of acyclic conjunctive queries
• Learning schema mappings
• Degrees of acyclicity for hypergraphs and relational database schemes
• Learnability and the Vapnik-Chervonenkis dimension
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• A theory of the learnable
• Computational limitations on learning from examples
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
• The Product Homomorphism Problem and Applications

This page was built for publication: On the non-efficient PAC learnability of conjunctive queries