Learning via queries in [+, <]

DOI10.2307/2275176zbMath0774.03023MaRDI QIDQ4008746

William I. Gasarch, Robert M. Solovay, Mark G. Pleszkoch

Publication date: 27 September 1992

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275176

zbMATH Keywords

recursive functions; inductive inference machine; effective procedures for quantifier elimination; query inductive inference

Mathematics Subject Classification ID

03B25: Decidability of theories and sets of sentences

03D15: Complexity of computation (including implicit computational complexity)

03F30: First-order arithmetic and fragments

03D20: Recursive functions and relations, subrecursive hierarchies

03D10: Turing machines and related notions

03C10: Quantifier elimination, model completeness, and related topics

Related Items

Inferring answers to queries, Taming teams with mind changes, One-shot learners using negative counterexamples and nearest positive examples, Learning via queries and oracles, Automata techniques for query inference machines, Refuting learning revisited., Recursion theoretic models of learning: Some results and intuitions

Cites Work

• Comparison of identification criteria for machine inductive inference
• Probability and plurality for aggregations of learning machines
• Saving the phenomena: Requirements that inductive inference machines not contradict known data
• On the complexity of inductive inference
• The Power of Pluralism for Automatic Program Synthesis
• Language identification in the limit