To access the full text documents, please follow this link: 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
Report
         

Show full item record

Related documents

Other documents of the same author

Arias Vicente, Marta; Troncoso, Alicia; Riquelme, José C.
Capdevila Pujol, Joan; Arias Vicente, Marta; Arratia Quesada, Argimiro Alejandro
 

Coordination

 

Supporters