DocumentCode
2777562
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
fYear
1990
fDate
22-24 Oct 1990
Firstpage
186
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location
St. Louis, MO
Print_ISBN
0-8186-2082-X
Type
conf
DOI
10.1109/FSCS.1990.89537
Filename
89537
Link To Document