2026-04-13T06:44:37Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/879702025-07-17T10:03:48Zcom_2072_1033col_2072_452950

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 Àrees temàtiques de la UPC::Informàtica::Intel·ligència artificial Horn logic Minimal representation Query learning 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. Postprint (published version) 2009-05 External research report Arias, M., Balcázar, J. L. "Canonical Horn representations and query learning". 2009. https://hdl.handle.net/2117/87970 eng LSI-09-18-R Open Access 20 p. application/pdf