Prediction-hardness of acyclic conjunctive queries

DOI10.1016/J.TCS.2005.09.006MaRDI QIDQ2581365zbMATH OpenOpenAlexFDO

Authors Kouichi Hirata

Publication date 10 January 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.09.006

zbMATH Keywords

Acyclic conjunctive queryInductive logic programmingPredictionPrediction-preserving reductionSubsumption

Mathematics Subject Classification ID

Database theory (68P15)

Recommendations

• scientific article; zbMATH DE number 2080453
• The complexity of acyclic conjunctive queries
• Conjunctive query containment revisited
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• Learnability of solutions to conjunctive queries

Cites work

• A theory of the learnable
• Conjunctive query containment revisited
• Cryptographic limitations on learning Boolean formulae and finite automata
• Degrees of acyclicity for hypergraphs and relational database schemes
• First-order \(jk\)-clausal theories are PAC-learnable
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1104356 (Why is no real title available?)
• scientific article; zbMATH DE number 1149414 (Why is no real title available?)
• scientific article; zbMATH DE number 1149415 (Why is no real title available?)
• scientific article; zbMATH DE number 2080453 (Why is no real title available?)
• scientific article; zbMATH DE number 1453036 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Learning action strategies for planning domains
• Learning function-free Horn expressions
• Learning logic programs with structured background knowledge
• On the Desirability of Acyclic Database Schemes
• Pac-learning non-recursive Prolog clauses
• Prediction-preserving reducibility
• Subsumption and implication
• The complexity of acyclic conjunctive queries

Cited in

(2)

• scientific article; zbMATH DE number 2080453 (Why is no real title available?)
• On the non-efficient PAC learnability of conjunctive queries

This page was built for publication: Prediction-hardness of acyclic conjunctive queries

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