Learning Conjunctions of Horn Clauses

Dana Angluin, Michael Frazier, Leonard Pitt

Research output: Contribution to journalArticle

Abstract

An algorithm is presented for learning the class of Boolean formulas that are expressible as conjunctions of Horn clauses. (A Horn clause is a disjunction of literals, all but at most one of which is a negated variable.) The algorithm uses equivalence queries and membership queries to produce a formula that is logically equivalent to the unknown formula to be learned. The amount of time used by the algorithm is polynomial in the number of variables and the number of clauses in the unknown formula.

Original languageEnglish (US)
Pages (from-to)147-164
Number of pages18
JournalMachine Learning
Volume9
Issue number2
DOIs
StatePublished - Jul 1992

Keywords

  • Propositional Horn sentences
  • equivalence queries
  • exact identification
  • membership queries
  • polynomial time learning

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Learning Conjunctions of Horn Clauses'. Together they form a unique fingerprint.

  • Cite this

    Angluin, D., Frazier, M., & Pitt, L. (1992). Learning Conjunctions of Horn Clauses. Machine Learning, 9(2), 147-164. https://doi.org/10.1023/A:1022689015665