University of Limerick
Browse
Bordeaux_2012_computers.pdf (248.33 kB)

Knowledge compilation with empowerment

Download (248.33 kB)
conference contribution
posted on 2013-01-02, 11:34 authored by Lucas Bordeaux, Joao Marques-Silva
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.

History

Publication

38th International Conference on Current Trends in Theory and Practice of Computer Science. Lecture Notes in Computer Science;7147, pp. 612-614

Publisher

Springer

Note

peer-reviewed

Other Funding information

SFI, FCT, INESC-ID

Rights

The original publication is available at www.springerlink.com

Language

English

Usage metrics

    University of Limerick

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC