Constraint satisfaction with succinctly specified relations

DOI10.1016/J.JCSS.2010.04.003MaRDI QIDQ1959431zbMATH OpenOpenAlexFDO

Authors Hubie Chen, Martin Grohe

Publication date 7 October 2010

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2006/802/

zbMATH Keywords

complexityconstraint satisfactiondecision diagramssuccinct representations

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Computational Complexity of Constraint Satisfaction
• Methods and Applications of Artificial Intelligence
• Tractability in constraint satisfaction problems: a survey
• Relatively quantified constraint satisfaction
• The complexity of constraint satisfaction problems (invited talk)

Cites work

• scientific article; zbMATH DE number 1487982 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A comparison of structural CSP decomposition methods
• A unified theory of structural tractability for constraint satisfaction problems
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Constraints, consistency and closure
• Hypertree decompositions and tractable queries
• Hypertree-width and related hypergraph invariants
• Principles and Practice of Constraint Programming – CP 2004
• Query evaluation via tree-decompositions
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Theory and Applications of Satisfiability Testing
• Tractable structures for constraint satisfaction with truth tables
• Tree clustering for constraint networks

Cited in

(9)

• Structural decompositions for problems with global constraints
• Tractability in constraint satisfaction problems: a survey
• Tractable structures for constraint satisfaction with truth tables
• The complexity of constraint satisfaction problems for small relation algebras
• The power of propagation: when GAC is enough
• On the complexity of existential positive queries
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• Sum-of-Products with Default Values: Algorithms and Complexity Results
• Alloy*: a general-purpose higher-order relational constraint solver

This page was built for publication: Constraint satisfaction with succinctly specified relations

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