A Logical Approach to Constraint Satisfaction

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

Mathematics Subject Classification ID

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)

Semantic Acyclicity on Graph Databases ⋮ The complexity of the list homomorphism problem for graphs

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