{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:51Z","timestamp":1781078031753,"version":"3.54.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,11]],"date-time":"2020-02-11T00:00:00Z","timestamp":1581379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003451","name":"University of the Basque Country","doi-asserted-by":"crossref","award":["GIU18\/182"],"award-info":[{"award-number":["GIU18\/182"]}],"id":[{"id":"10.13039\/501100003451","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MINECO","award":["TIN2017-86727-C2-2-R"],"award-info":[{"award-number":["TIN2017-86727-C2-2-R"]}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"crossref","award":["245288\/2012-0"],"award-info":[{"award-number":["245288\/2012-0"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,3,31]]},"abstract":"<jats:p>A major problem in computational learning theory is whether the class of formulas in conjunctive normal form (CNF) is efficiently learnable. Although it is known that this class cannot be polynomially learned using either membership or equivalence queries alone, it is open whether the CNF class can be polynomially learned using both types of queries. One of the most important results concerning a restriction of the CNF class is that propositional Horn formulas are polynomial time learnable in Angluin\u2019s exact learning model with membership and equivalence queries. In this work, we push this boundary and show that the class of multivalued dependency formulas (MVDF), which non-trivially extends propositional Horn, is polynomially learnable from interpretations. We then provide a notion of reduction between learning problems in Angluin\u2019s model, showing that a transformation of the algorithm suffices to efficiently learn multivalued database dependencies from data relations. We also show via reductions that our main result extends well known previous results and allows us to find alternative solutions for them.<\/jats:p>","DOI":"10.1145\/3369930","type":"journal-article","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T12:28:17Z","timestamp":1582633697000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Exact Learning"],"prefix":"10.1145","volume":"12","author":[{"given":"Montserrat","family":"Hermo","sequence":"first","affiliation":[{"name":"Languages and Information Systems, University of the Basque Country, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ana","family":"Ozaki","sequence":"additional","affiliation":[{"name":"KRDB Research Centre, Free University of Bozen-Bolzano and TU Dresden, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,2,11]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022821128753"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022692615781"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992675"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1026"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-011-5248-5"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 7th International Conference on Discovery Science (DS\u201904)","author":"Jos\u00e9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1164"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.216.0534"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/320557.320571"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1216155.1216159"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-307-3.50022-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509976"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24486-0_5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.11.018"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1998.655802"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/int.4550070703"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28426"},{"key":"e_1_2_1_22_1","volume-title":"Kearns and Umesh Vazirani","author":"Michael","year":"1994"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Conference on Artificial Intelligence (AAAI\u201916)","author":"Konev Boris","year":"2016"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.01.011"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00354-015-0301-8"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.07.007"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116827"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-023X(94)90023-X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1149"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 3rd Annual Structure in Complexity Theory Conference","author":"Pitt Leonard","year":"1988"},{"key":"e_1_2_1_31_1","unstructured":"V\u00edctor Lav\u00edn Puente. 2015. Learning sets of antecedent-restricted functional and multivalued dependencies with queries. Theory Comput. Syst. (2015) 1--17.  V\u00edctor Lav\u00edn Puente. 2015. Learning sets of antecedent-restricted functional and multivalued dependencies with queries. Theory Comput. Syst. (2015) 1--17."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322263"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_2_1_34_1","first-page":"211","article-title":"A framework for polynomial-time query learnability","volume":"27","author":"Watanabe Osamu","year":"1994","journal-title":"Theory Comput. Syst."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369930","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3369930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:27Z","timestamp":1750203867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369930"}},"subtitle":["On the Boundary between Horn and CNF"],"short-title":[],"issued":{"date-parts":[[2020,2,11]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3369930"],"URL":"https:\/\/doi.org\/10.1145\/3369930","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,11]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}