A Logical Approach to Constraint Satisfaction

DOI10.1007/978-3-540-92800-3_6MaRDI QIDQ5504702zbMATH OpenOpenAlexFDO

Authors 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

Logic in computer science (03B70) Database theory (68P15) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Methods and Applications of Artificial Intelligence
• Conjunctive-query containment and constraint satisfaction
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The logic of constraint satisfaction
• scientific article; zbMATH DE number 1008453

Cites work

• A comparison of structural CSP decomposition methods
• A linear time algorithm for finding tree-decompositions of small treewidth
• A Sufficient Condition for Backtrack-Free Search
• An optimal k-consistency algorithm
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Bucket elimination: A unifying framework for reasoning
• Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection
• Classifying the Complexity of Constraints Using Finite Algebras
• Complexity of Finding Embeddings in a k-Tree
• Computer Science Logic
• Conjunctive query containment revisited
• Conjunctive-query containment and constraint satisfaction
• Constraint satisfaction from a deductive viewpoint
• Constraint tightness and looseness versus local and global consistency
• Datalog vs first-order logic
• Decomposing constraint satisfaction problems using database techniques
• Experimental evaluation of preprocessing algorithms for constraint satisfaction problems
• Finite model theory and its applications.
• From local to global consistency
• Graph minors. IV: Tree-width and well-quasi-ordering
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1487982 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• Hypertree decompositions and tractable queries
• Linear time solvable optimization problems on graphs of bounded clique-width
• Monotone monadic SNP and constraint satisfaction
• On the complexity of H-coloring
• On the Structure of Polynomial Time Reducibility
• Optimization, approximation, and complexity classes
• Principles of Constraint Programming
• Synthesizing constraint expressions
• The complexity of acyclic conjunctive queries
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Tree clustering for constraint networks
• Undecidable optimization problems for database logic programs
• When is the evaluation of conjunctive queries tractable?

Cited in

(17)

• Reasoning from last conflict(s) in constraint programming
• Constraint satisfaction from a deductive viewpoint
• The logic of constraint satisfaction
• Conjunctive-query containment and constraint satisfaction
• Logical compactness and constraint satisfaction problems
• Semantic acyclicity on graph databases
• scientific article; zbMATH DE number 4152150 (Why is no real title available?)
• A perspective of constraint-based reasoning. An introductory tutorial
• scientific article; zbMATH DE number 1222101 (Why is no real title available?)
• scientific article; zbMATH DE number 1256705 (Why is no real title available?)
• scientific article; zbMATH DE number 1059315 (Why is no real title available?)
• Computer Science Logic
• Methods and Applications of Artificial Intelligence
• Computer Science Logic
• Constraint Satisfaction, Logic and Forbidden Patterns
• Constraint satisfaction, graph isomorphism, and the pebbling comonad
• The complexity of the list homomorphism problem for graphs

This page was built for publication: A Logical Approach to Constraint Satisfaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5504702)