Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Knowledge Compilation with Empowerment
verfasst von : Lucas Bordeaux, Joao Marques-Silva
Erschienen in: SOFSEM 2012: Theory and Practice of Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
When we encode constraints as Boolean formulas, a natural question is whether the encoding ensures a “propagation completeness” property: is the basic unit propagation mechanism able to deduce all the literals that are logically valid? We consider the problem of automatically finding encodings with this property. Our goal is to compile a naïve definition of a constraint into a good, propagation-complete encoding. Well-known Knowledge Compilation techniques from AI can be used for this purpose, but the constraints for which they can produce a polynomial size encoding are few. We show that the notion of
empowerment
recently introduced in the SAT literature allows producing encodings that are shorter than with previous techniques, sometimes exponentially.