English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/132347
Share/Impact:
Statistics
logo share SHARE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE
Exportar a otros formatos:

DC FieldValueLanguage
dc.contributor.authorAnsotegui, Carlos-
dc.contributor.authorBonet, Maria Luisa-
dc.contributor.authorGiráldez-Crú, Jesús-
dc.contributor.authorLevy, Jordi-
dc.date.accessioned2016-05-18T16:03:30Z-
dc.date.available2016-05-18T16:03:30Z-
dc.date.issued2014-07-19-
dc.identifierdoi: 10.1007/978-3-319-08587-6_8-
dc.identifierisbn: 978-331908586-9-
dc.identifier.citationLecture Notes in Computer Science, vol. 8562. Automated Reasoning, 7th International Joint Conference, IJCAR 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 19-22, 2014. Proceedings, pp.107-121-
dc.identifier.urihttp://hdl.handle.net/10261/132347-
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.-
dc.publisherSpringer-
dc.relation.isversionofPostprint-
dc.rightsopenAccess-
dc.subjectSAT instances-
dc.subjectFractal dimension-
dc.subjectSelf-similar-
dc.subjectSAT-solving-
dc.subjectSAT solvers-
dc.subjectPrecise definition-
dc.titleThe Fractal Dimension of SAT Formulas-
dc.typecomunicación de congreso-
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-319-08587-6_8-
dc.date.updated2016-05-18T16:03:31Z-
dc.description.versionPeer Reviewed-
dc.language.rfc3066eng-
dc.relation.csic-
Appears in Collections:(IIIA) Comunicaciones congresos
Files in This Item:
File Description SizeFormat 
LNCS8562_107-121.pdf687,05 kBUnknownView/Open
Show simple item record
 


WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.