A Logical Approach to Constraint Satisfaction
From MaRDI portal
Publication:5504702
DOI10.1007/978-3-540-92800-3_6zbMath1171.03322OpenAlexW1527777107MaRDI QIDQ5504702
Phokion G. Kolaitis, Moshe Y. Vardi
Publication date: 22 January 2009
Published in: Complexity of Constraints (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92800-3_6
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Logic in computer science (03B70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hypertree decompositions and tractable queries
- Finite model theory and its applications.
- On the complexity of H-coloring
- Constraint satisfaction from a deductive viewpoint
- Tree clustering for constraint networks
- An optimal k-consistency algorithm
- Optimization, approximation, and complexity classes
- From local to global consistency
- Decomposing constraint satisfaction problems using database techniques
- Experimental evaluation of preprocessing algorithms for constraint satisfaction problems
- Datalog vs first-order logic
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Conjunctive query containment revisited
- A comparison of structural CSP decomposition methods
- Conjunctive-query containment and constraint satisfaction
- Linear time solvable optimization problems on graphs of bounded clique-width
- Bucket elimination: A unifying framework for reasoning
- Graph minors. IV: Tree-width and well-quasi-ordering
- Undecidable optimization problems for database logic programs
- The complexity of acyclic conjunctive queries
- Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- Principles of Constraint Programming
- Complexity of Finding Embeddings in a k-Tree
- A Sufficient Condition for Backtrack-Free Search
- On the Structure of Polynomial Time Reducibility
- Synthesizing constraint expressions
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Constraint tightness and looseness versus local and global consistency
- When is the evaluation of conjunctive queries tractable?
- A linear time algorithm for finding tree-decompositions of small treewidth
- Monotone monadic SNP and constraint satisfaction
- Computer Science Logic
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
This page was built for publication: A Logical Approach to Constraint Satisfaction