A framework for polynomial-time query learnability

DOI10.1007/BF01578843zbMath0809.68097MaRDI QIDQ4298370

Osamu Watanabe

Publication date: 26 July 1994

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

zbMATH Keywords

query learningpolynomial-time query learning

Mathematics Subject Classification ID

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

Related Items (7)

The query complexity of learning DFA ⋮ PACS, simple-PAC and query learning ⋮ Structural analysis of polynomial-time query learnability ⋮ On the complexity of small description and related topics ⋮ The complexity of learning minor closed graph classes ⋮ A new abstract combinatorial dimension for exact learning via queries ⋮ The complexity of learning concept classes with polynomial general dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Prediction-preserving reducibility
• Learning context-free grammars from structural data in polynomial time
• Learning regular sets from queries and counterexamples
• Finding patterns common to a set of strings
• When won't membership queries help?
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Computational limitations on learning from examples
• The Knowledge Complexity of Interactive Proof Systems
• Structural analysis of polynomial-time query learnability
• Language identification in the limit

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