Learning conjunctions of horn clauses

Dana Angluin, Michael Frazier, Leonard Pitt

Research output: Contribution to journalConference articlepeer-review

Abstract

An algorithm for learning the class of Boolean formulas that are expressible as conjunctions of Horn clauses is presented. (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)186-192
Number of pages7
JournalIEEE Transactions on Industry Applications
Volume27
Issue number1 pt 1
StatePublished - Jan 1991
Externally publishedYes
Event1989 Industry Applications Society Annual Meeting - San Diego, CA, USA
Duration: Oct 1 1989Oct 5 1989

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Industrial and Manufacturing Engineering
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Learning conjunctions of horn clauses'. Together they form a unique fingerprint.

Cite this