Title :
Learning conjunctions of Horn clauses
Author :
Angluin, Dana ; Frazier, Michael ; Pitt, L.
Author_Institution :
Dept. of Comput. Sci., Yale Univ., New Haven, CT, USA
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
Keywords :
Boolean functions; learning systems; Boolean formulas; Horn clause conjunctions; Horn sentence; clauses; disjunction of literals; equivalence queries; learning algorithm; membership queries; negated variable; polynomial time complexity; unknown formula; Computer science; Inference algorithms; Marine vehicles; Polynomials; Protocols;
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
DOI :
10.1109/FSCS.1990.89537
