Automata techniques for query inference machines

Annals of Pure and Applied Logic 117 (1-3):169-201 (2002)


In prior papers the following question was considered: which classes of computable sets can be learned if queries about those sets can be asked by the learner? The answer depended on the query language chosen. In this paper we develop a framework for studying this question. Essentially, once we have a result for queries to [S,<]2, we can obtain the same result for many different languages. We obtain easier proofs of old results and several new results. An earlier result we have an easier proof of: the set of computable sets cannot be learned with queries to the language [+,<] . A new result: the set of computable sets cannot be learned with queries to the language [+,<,POWa] where POWa is the predicate that tests if a number is a power of a

Download options


    Upload a copy of this work     Papers currently archived: 72,694

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

5 (#1,211,627)

6 months
1 (#388,311)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

Similar books and articles

The Complexity of Learning SUBSEQ(A).Stephen Fenner, William Gasarch & Brian Postow - 2009 - Journal of Symbolic Logic 74 (3):939-975.
Iterating Semantic Automata.Shane Steinert-Threlkeld & I. I. I. Thomas F. Icard - 2013 - Linguistics and Philosophy 36 (2):151-173.
Some Thoughts on Akin's Spiteful Computer.Ben Goertzel - 1994 - Minds and Machines 4 (1):75-80.
Query Graphs with Cuts: Mathematical Foundations.Frithjof Dau - 2004 - In A. Blackwell, K. Marriott & A. Shimojima (eds.), Diagrammatic Representation and Inference. Springer. pp. 32--50.
Robotics.Hans Moravec - unknown - Encyclopaedia Britannica Online.
A Dao of Technology?Barry Allen - 2010 - Dao: A Journal of Comparative Philosophy 9 (2):151-160.
Towards a More General Concept of Inference.Ivo Pezlar - 2014 - Logica Universalis 8 (1):61-81.
Modifiable Automata Self-Modifying Automata.J.-P. Moulin - 1992 - Acta Biotheoretica 40 (2-3):195-204.
Domesticating Animal Theory.John Muckelbauer - 2011 - Philosophy and Rhetoric 44 (1):95-100.