Learning via queries in $\lbrack +,

Journal of Symbolic Logic 57 (1):53-81 (1992)

Authors
Robert Solovay
University of California, Berkeley
Abstract
We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols $\lbrack +, . The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in $\lbrack +, . Additionally, we resolve an open question in [7] about passive versus active learning
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275176
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 48,824
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Learning Via Queries and Oracles.Frank Stephan - 1998 - Annals of Pure and Applied Logic 94 (1-3):273-296.
Automata Techniques for Query Inference Machines.William Gasarch & Geoffrey R. Hird - 2002 - Annals of Pure and Applied Logic 117 (1-3):169-201.

Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
220 ( #35,161 of 2,309,317 )

Recent downloads (6 months)
1 ( #761,345 of 2,309,317 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature