Name
Abstract | ||
|---|---|---|
Regular-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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.dam.2005.10.020 | Discrete Applied Mathematics |
Keywords | Field | DocType |
sat algorithm,combinatorial problem solving,many-valued logic,combinatorial problem,good property,sat that-by,regular-sat inherits,good compromise,many-valued approach,solvers,constraint programming language,satisfiability,practical computational advantage,computational cost,benchmark problems-provide evidence,many valued logic,constraint programming,expressive power,phase transition | Discrete mathematics,Similitude,Computer science,Satisfiability,Constraint programming,Algorithm,Theoretical computer science,Formalism (philosophy),Many-valued logic,Expressive power,Encoding (memory) | Journal |
Volume | Issue | ISSN |
155 | 12 | Discrete Applied Mathematics |
Citations | PageRank | References |
4 | 0.42 | 24 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ramón Béjar | 1 | 305 | 36.72 |
| Felip Manyà | 2 | 787 | 59.52 |
| Alba Cabiscol | 3 | 31 | 3.86 |
| Cèsar Ferníndez | 4 | 4 | 0.42 |
| Carla P. Gomes | 5 | 2344 | 179.21 |