Approximating propositional knowledge with affine formulasReportar como inadecuado

Approximating propositional knowledge with affine formulas - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Equipe MAD - Laboratoire GREYC - UMR6072 GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen

Abstract : 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.

Autor: Bruno Zanuttini -



Documentos relacionados