Universitat de Lleida
    • English
    • català
    • español
  • català 
    • English
    • català
    • español
  • Inicia la sessió
Repositori Obert UdL
Visualitza l'element 
  •   Inici
  • Recerca
  • Informàtica i Enginyeria Industrial
  • Articles publicats (Informàtica i Enginyeria Industrial)
  • Visualitza l'element
  •   Inici
  • Recerca
  • Informàtica i Enginyeria Industrial
  • Articles publicats (Informàtica i Enginyeria Industrial)
  • Visualitza l'element
JavaScript is disabled for your browser. Some features of this site may not work without it.

The Fractal Dimension of SAT Formulas

Thumbnail
Visualitza/Obre
Postprint (789.3Kb)
Data de publicació
2014
Autor/a
Ansótegui Gil, Carlos José
Bonet, Maria Luisa
Giráldez-Cru, Jesús
Levy, Jordi
Impacte


Logo de Web of Science    citacions a Web of Science

Logo d'Scopus    citacions a Scopus

Logo de Google Acadèmic  Google Acadèmic
Compartir
Exportar a Mendeley
Metadades
Mostra el registre d'unitat complet
Resum
Modern 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.
URI
http://hdl.handle.net/10459.1/65063
DOI
https://doi.org/10.1007/978-3-319-08587-6_8
És part de
Lecture Notes in Computer Science, 2014, vol. 8562, p. 107-121
Col·leccions
  • Publicacions de projectes de recerca del Plan Nacional [1767]
  • Articles publicats (Informàtica i Enginyeria Industrial) [670]

Contacteu amb nosaltres | Envia comentaris | Avís legal
© 2019 BiD. Universitat de Lleida
Metadades subjectes a
 

 

Explora

Tot el repositoriComunitats i col·leccionsPer data d'edicióAutorsTítolsMatèriesAquesta col·leccióPer data d'edicióAutorsTítolsMatèries

Estadístiques

Veure estadístiques d'ús

D'interès

Política institucional d'accés obertDiposita les teves publicacionsDiposita dades de recercaSuport a la recerca

Contacteu amb nosaltres | Envia comentaris | Avís legal
© 2019 BiD. Universitat de Lleida
Metadades subjectes a