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 :
بازگشت