Automata techniques for query inference machines

✍ Scribed by William Gasarch; Geoffrey R. Hird

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 248 KB
• Volume: 117
• Category: Article
• ISSN: 0168-0072
• DOI: 10.1016/s0168-0072(01)00115-4

✦ Synopsis

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 (reductions) for studying this question. Essentially, once we have a result for queries to [S; ¡ ] 2 , we can obtain the same result for many di erent 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 [+; ¡ ] (in notation: COMP ∈ QEX [+; ¡ ]). 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.