Show simple item record

dc.contributor.authorAnsótegui Gil, Carlos José
dc.contributor.authorBonet, Maria Luisa
dc.contributor.authorGiráldez-Cru, Jesús
dc.contributor.authorLevy, Jordi
dc.date.accessioned2018-11-09T09:49:33Z
dc.date.available2018-11-09T09:49:33Z
dc.date.issued2014
dc.identifier.issn0302-9743
dc.identifier.urihttp://hdl.handle.net/10459.1/65063
dc.description.abstractModern SAT solvers have experienced a remarkable progress on solving industrial instances. Most of the techniques have been developed after an intensive experimental process. It is believed that these techniques exploit the underlying structure of industrial instances. However, there is not a precise definition of the notion of structure. Recently, there have been some attempts to analyze this structure in terms of complex networks, with the long-term aim of explaining the success of SAT solving techniques, and possibly improving them. We study the fractal dimension of SAT instances with the aim of complementing the model that describes the structure of industrial instances. We show that many industrial families of formulas are self-similar, with a small fractal dimension. We also show how this dimension is affected by the addition of learnt clauses during the execution of SAT solvers.ca_ES
dc.description.sponsorshipThis research has been partially founded by the MINECO research project TASSAT (TIN2010-20967).ca_ES
dc.language.isoengca_ES
dc.publisherSpringer Verlagca_ES
dc.relationMICINN/PN2008-2011/TIN2010-20967
dc.relation.isformatofVersió postprint del document publicat a https://doi.org/10.1007/978-3-319-08587-6_8ca_ES
dc.relation.ispartofLecture Notes in Computer Science, 2014, vol. 8562, p. 107-121ca_ES
dc.rights(c) Springer Verlag, 2014ca_ES
dc.subjectSAT instancesca_ES
dc.subjectFractal dimensionca_ES
dc.subjectSelf-similarca_ES
dc.subjectSAT-solvingca_ES
dc.titleThe Fractal Dimension of SAT Formulasca_ES
dc.typeinfo:eu-repo/semantics/articleca_ES
dc.type.versioninfo:eu-repo/semantics/acceptedVersionca_ES
dc.rights.accessRightsinfo:eu-repo/semantics/openAccessca_ES
dc.identifier.doihttps://doi.org/10.1007/978-3-319-08587-6_8


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record