English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/132347
Compartir / Impacto:
Estadísticas
Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Título

The Fractal Dimension of SAT Formulas

AutorAnsótegui̊, Carlos; Bonet, Maria Luisa; Giráldez-Cru, Jesús; Levy, Jordi
Palabras claveSAT instances
Fractal dimension
Self-similar
SAT-solving
SAT solvers
Precise definition
Fecha de publicación19-jul-2014
EditorSpringer
Citación Lecture 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
ResumenModern 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.
URIhttp://hdl.handle.net/10261/132347
DOI10.1007/978-3-319-08587-6_8
Identificadoresdoi: 10.1007/978-3-319-08587-6_8
isbn: 978-331908586-9
Aparece en las colecciones: (IIIA) Comunicaciones congresos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
LNCS8562_107-121.pdf687,05 kBUnknownVisualizar/Abrir
Mostrar el registro completo
 


NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.