Treffer: Regular-SAT : A many-valued approach to solving combinatorial problems
Title:
Regular-SAT : A many-valued approach to solving combinatorial problems
Authors:
Source:
SAT 2001, the fourth international symposium on the theory and applications of satisfiability testingDiscrete applied mathematics. 155(12):1613-1626
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 31 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Logiciel, Software, Langages de programmation, Programming languages, Intelligence artificielle, Artificial intelligence, Résolution de problèmes, jeux, Problem solving, game playing, Algorithme, Algorithm, Algoritmo, Benchmark, Benchmarks, Combinatoire, Combinatorics, Combinatoria, Coût, Costs, Coste, Informatique théorique, Computer theory, Informática teórica, Langage programmation, Programming language, Lenguaje programación, Logique, Logic, Lógica, Optimisation, Optimization, Optimización, Paradigme, Paradigm, Paradigma, Performance, Rendimiento, Problème combinatoire, Combinatorial problem, Problema combinatorio, Résolution problème, Problem solving, Resolución problema, Résultat expérimental, Experimental result, Resultado experimental, Similitude, Similarity, Similitud, Transition phase, Phase transitions, Transición fase, 68N15, 68T20, 68Wxx, CSP, Programmation contrainte, Puissance expressive, SAT, Satisfiabilité, Terme, Combinatorial problem solving, Many-valued logic, Satisfiability, Solvers
Document Type:
Konferenz
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computer Science, Universitat de LLeida, Jaume II 69, 25001 LLeida, Spain
IIIA, Artificial Intelligence Research Institute,CSIC, Spanish Council,for Scientific-Research,Campus UAB, 08193 Bellaterra, Spain
Departmentt of Computer Science, Cornell University, Ithaca, NY 14853, United States
IIIA, Artificial Intelligence Research Institute,CSIC, Spanish Council,for Scientific-Research,Campus UAB, 08193 Bellaterra, Spain
Departmentt of Computer Science, Cornell University, Ithaca, NY 14853, United States
ISSN:
0166-218X
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Mathematics
Mathematics
Accession Number:
edscal.18962802
Database:
PASCAL Archive
Weitere Informationen
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.