15
^{th} European Conference on Artificial Intelligence |

July 21-26 2002 Lyon France |
||

[full paper] |

**Approximating Propositional Knowledge with Affine Formulas**

*Bruno Zanuttini*We consider the use of affine formulas, i.e., conjonctions of linear equations modulo 2, for approximating propositional knowledge. These formulas are very close to CNF formulas, and allow for efficient reasoning ; moreover, they can be minimized efficiently. We show that this class of formulas is identifiable and PAC-learnable from examples, that an affine least upper bound of a relation can be computed in polynomial time and a greatest lower bound with the maximum number of models in subexponential time. All these results are better than those for, e.g., Horn formulas, which are often considered for representing or approximating propositional knowledge. For all these reasons we argue that affine formulas are good candidates for approximating propositional knowledge.

*Keywords:*Knowledge Representation, Knowledge Acquisition, Machine Learning

*Citation:* Bruno Zanuttini: Approximating Propositional Knowledge with Affine Formulas. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.287-291.

ECAI-2002 is organised by the