University of Limerick Institutional Repository

Knowledge compilation with empowerment

DSpace Repository

Show simple item record

dc.contributor.author Bordeaux, Lucas
dc.contributor.author Marques-Silva, Joao
dc.date.accessioned 2013-01-02T11:34:27Z
dc.date.available 2013-01-02T11:34:27Z
dc.date.issued 2012
dc.identifier.uri http://hdl.handle.net/10344/2767
dc.description peer-reviewed en_US
dc.description.abstract 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. en_US
dc.language.iso eng en_US
dc.publisher Springer en_US
dc.relation.ispartofseries 38th International Conference on Current Trends in Theory and Practice of Computer Science. Lecture Notes in Computer Science;7147, pp. 612-614
dc.relation.uri http://dx.doi.org/10.1007/978-3-642-27660-6_50
dc.rights The original publication is available at www.springerlink.com en_US
dc.subject software engineering en_US
dc.subject database management en_US
dc.subject computer communicatons en_US
dc.title Knowledge compilation with empowerment en_US
dc.type info:eu-repo/semantics/conferenceObject en_US
dc.type.supercollection all_ul_research en_US
dc.type.supercollection ul_published_reviewed en_US
dc.contributor.sponsor SFI en_US
dc.contributor.sponsor FCT
dc.contributor.sponsor INESC-ID
dc.relation.projectid BEACON 09/IN.1/I2618 en_US
dc.relation.projectid ATTEST (CMU-PT/ELE/0009/2009)
dc.relation.projectid POLARIS (PTDC/EIA-CCO/-123051/2010)
dc.rights.accessrights info:eu-repo/semantics/openAccess en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search ULIR


Browse

My Account

Statistics