%0 Journal Article %1 journals/corr/abs-1807-06149 %A Borchmann, Daniel %A Hanika, Tom %A Obiedkov, Sergei %D 2018 %J CoRR %K exploration fca myown pac preprint %T Probably approximately correct learning of Horn envelopes from queries. %U http://dblp.uni-trier.de/db/journals/corr/corr1807.html#abs-1807-06149 %V abs/1807.06149 %X We propose an algorithm for learning the Horn envelope of an arbitrary domain using an expert, or an oracle, capable of answering certain types of queries about this domain. Attribute exploration from formal concept analysis is a procedure that solves this problem, but the number of queries it may ask is exponential in the size of the resulting Horn formula in the worst case. We recall a well-known polynomial-time algorithm for learning Horn formulas with membership and equivalence queries and modify it to obtain a polynomial-time probably approximately correct algorithm for learning the Horn envelope of an arbitrary domain.

@article{journals/corr/abs-1807-06149, abstract = {We propose an algorithm for learning the Horn envelope of an arbitrary domain using an expert, or an oracle, capable of answering certain types of queries about this domain. Attribute exploration from formal concept analysis is a procedure that solves this problem, but the number of queries it may ask is exponential in the size of the resulting Horn formula in the worst case. We recall a well-known polynomial-time algorithm for learning Horn formulas with membership and equivalence queries and modify it to obtain a polynomial-time probably approximately correct algorithm for learning the Horn envelope of an arbitrary domain.}, added-at = {2018-08-02T09:26:25.000+0200}, author = {Borchmann, Daniel and Hanika, Tom and Obiedkov, Sergei}, biburl = {https://www.bibsonomy.org/bibtex/24780ba2a352bc1739173ce604b19a857/tomhanika}, ee = {http://arxiv.org/abs/1807.06149}, interhash = {b21544ec9141f6fb12762d40e3673fbc}, intrahash = {4780ba2a352bc1739173ce604b19a857}, journal = {CoRR}, keywords = {exploration fca myown pac preprint}, note = {cite arxiv:1807.06149Comment: 21 pages, 1 figure}, timestamp = {2020-02-21T11:58:39.000+0100}, title = {Probably approximately correct learning of Horn envelopes from queries.}, url = {http://dblp.uni-trier.de/db/journals/corr/corr1807.html#abs-1807-06149}, volume = {abs/1807.06149}, year = 2018 }