Name
Abstract | ||
|---|---|---|
We describe an alternative construction of an existing canonical representation for definite Horn theories, the Guigues-Duquenne basis (or GD basis), which minimizes a natural notion of implicational size. We extend the canonical representation to general Horn, by providing a reduction from definite to general Horn CNF. We show how this representation relates to two topics in query learning theory: first, we show that a well-known algorithm by Angluin, Frazier and Pitt that learns Horn CNF always outputs the GD basis independently of the counterexamples it receives; second, we build strong polynomial certificates for Horn CNF directly from the GD basis. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-04414-4_16 | ALT |
Keywords | Field | DocType |
query learning,canonical horn representation,gd basis,horn cnf,guigues-duquenne basis,alternative construction,canonical representation,general horn,implicational size,existing canonical representation,definite horn theory,general horn cnf,learning theory | Boolean function,Query learning,Discrete mathematics,Horn clause,Polynomial,Canonical form,Conjunctive normal form,Artificial intelligence,Counterexample,Mathematics,Machine learning,Propositional variable | Conference |
Volume | ISSN | ISBN |
5809 | 0302-9743 | 3-642-04413-1 |
Citations | PageRank | References |
7 | 0.60 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marta Arias | 1 | 165 | 15.62 |
| José L. Balcázar | 2 | 701 | 62.06 |