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

Canonical Horn representations and query learning
Arias Vicente, Marta; Balcázar Navarro, José Luis
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge
We describe an alternative construction of an existing canonical representation for definite Horn theories, the emph{Guigues-Duquenne} basis (or GD basis), which minimizes a natural notion of implicational size. We extend the canonical representation to general Horn, by providing a reduction from definite to general Horn CNF. We show how this representation relates to two topics in query learning theory: first, we show that a well-known algorithm by Angluin, Frazier and Pitt that learns Horn CNF always outputs the GD basis independently of the counterexamples it receives; second, we build strong polynomial certificates for Horn CNF directly from the GD basis.
Àrees temàtiques de la UPC::Informàtica::Intel·ligència artificial
Horn logic
Minimal representation
Query learning
info:eu-repo/semantics/publishedVersion
Informe
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Arias Vicente, Marta; Balcázar Navarro, José Luis; Tîrnauca, Cristina
Arias Vicente, Marta; Troncoso, Alicia; Riquelme, José C.