A framework for polynomial-time query learnability
From MaRDI portal
Publication:4298370
DOI10.1007/BF01578843zbMath0809.68097MaRDI QIDQ4298370
Publication date: 26 July 1994
Published in: Mathematical Systems Theory (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68T05: Learning and adaptive systems in artificial intelligence
Related Items
Structural analysis of polynomial-time query learnability, The complexity of learning concept classes with polynomial general dimension, The query complexity of learning DFA, A new abstract combinatorial dimension for exact learning via queries
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