Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/82131

Título:	Oracles and queries that are sufficient for exact learning
Autor/a:	Bhousty, Nader H.; Cleve, Richard; Gavaldà Mestre, Ricard; Kannan, Sampath; Tamon, Christino
Otros autores:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Abstract:	We show that the class of all circuits is exactly learnable in randomized expected polynomial time using weak subset and weak superset queries. This is a consequence of the following result which we consider to be of independent interest: circuits are exactly learnable in randomized expected polynomial time with equivalence queries and the aid of an NP oracle. We also show that circuits are exactly learnable in deterministic polynomial time with equivalence queries and a Sigma-3 oracle. The paper also contains results on: learning of DNF formulas, learning with membership queries, and an application to Structural Complexity Theory.
Materia(s):	-Àrees temàtiques de la UPC::Informàtica -Computational learning -DNF -NP-Oracle
Derechos:
Tipo de documento:	Artículo - Versión presentada Informe
Compartir:

Mostrar el registro completo del ítem