A framework for polynomial-time query learnability

DOI10.1007/BF01578843MaRDI QIDQ4298370zbMATH OpenFDO

Authors Osamu Watanabe

Publication date 26 July 1994

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01578843

zbMATH Keywords

polynomial-time query learningquery learning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• scientific article; zbMATH DE number 177810
• The consistency dimension and distribution-dependent learning from queries.
• Queries and concept learning
• Structural analysis of polynomial-time query learnability
• Publication:4955302

Cites work

• A theory of the learnable
• Computational limitations on learning from examples
• Finding patterns common to a set of strings
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 67617 (Why is no real title available?)
• scientific article; zbMATH DE number 177810 (Why is no real title available?)
• scientific article; zbMATH DE number 3640909 (Why is no real title available?)
• Language identification in the limit
• Learnability and the Vapnik-Chervonenkis dimension
• Learning context-free grammars from structural data in polynomial time
• Learning regular sets from queries and counterexamples
• Prediction-preserving reducibility
• Structural analysis of polynomial-time query learnability
• The Knowledge Complexity of Interactive Proof Systems
• When won't membership queries help?

Cited in

(11)

• The query complexity of learning DFA
• A new abstract combinatorial dimension for exact learning via queries
• LAQP: learning-based approximate query processing
• PACS, simple-PAC and query learning
• scientific article; zbMATH DE number 177810 (Why is no real title available?)
• Structural analysis of polynomial-time query learnability
• scientific article; zbMATH DE number 2068174 (Why is no real title available?)
• On the Power of Learning from k-Wise Queries
• On the complexity of small description and related topics
• The complexity of learning minor closed graph classes
• The complexity of learning concept classes with polynomial general dimension

This page was built for publication: A framework for polynomial-time query learnability

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