Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/162425
Share/Export:
logo share SHARE logo core CORE BASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE
Title

Regular-SAT: A many-valued approach to solving combinatorial problems

AuthorsBejar, Ramon; Manyà, Felip CSIC ORCID ; Cabiscol, Alba; Fernandez, Cesar; Gomes, Carla
KeywordsMany-valued logic
Solvers
Satisfiability
Combinatorial problem solving
Issue Date2007
PublisherElsevier
CitationDiscrete Applied Mathematics 155: 1613- 1626 (2007)
AbstractRegular-SAT is a constraint programming language between CSP and SAT that-by combining many of the good properties of each paradigm-offers a good compromise between performance and expressive power. Its similarity to SAT allows us to define a uniform encoding formalism, to extend existing SAT algorithms to Regular-SAT without incurring excessive overhead in terms of computational cost, and to identify phase transition phenomena in randomly generated instances. On the other hand, Regular-SAT inherits from CSP more compact and natural encodings that maintain more the structure of the original problem. Our experimental results-using a range of benchmark problems-provide evidence that Regular-SAT offers practical computational advantages for solving combinatorial problems. © 2006 Elsevier B.V. All rights reserved.
URIhttp://hdl.handle.net/10261/162425
DOI10.1016/j.dam.2005.10.020
Identifiersdoi: 10.1016/j.dam.2005.10.020
issn: 0166-218X
Appears in Collections:(IIIA) Artículos

Files in This Item:
File Description SizeFormat
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
View/Open
Show full item record
Review this work

Google ScholarTM

Check

Altmetric

Dimensions


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