Constraints, consistency and closure
From MaRDI portal
Publication:1274280
DOI10.1016/S0004-3702(98)00022-8zbMath0909.68076OpenAlexW1965377399MaRDI QIDQ1274280
Martin C. Cooper, David A. Cohen, Peter G. Jeavons
Publication date: 12 January 1999
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0004-3702(98)00022-8
Related Items (63)
Tractability in constraint satisfaction problems: a survey ⋮ The complexity of constraint satisfaction games and QCSP ⋮ Dualities and algebras with a near-unanimity term ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Learning intersection-closed classes with signatures ⋮ The Expressive Power of Binary Submodular Functions ⋮ Preserving near unanimity terms under products ⋮ Domain permutation reduction for constraint satisfaction problems ⋮ Properties of tree convex constraints ⋮ On planar valued CSPs ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Classes of submodular constraints expressible by graph cuts ⋮ Belief revision within fragments of propositional logic ⋮ Unnamed Item ⋮ On tree-preserving constraints ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Conservative constraint satisfaction re-revisited ⋮ A new line of attack on the dichotomy conjecture ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ Majority constraints have bounded pathwidth duality ⋮ Unnamed Item ⋮ The Expressive Power of Valued Constraints: Hierarchies and Collapses ⋮ Constraint satisfaction with succinctly specified relations ⋮ Learnability of quantified formulas. ⋮ The existence of a near-unanimity function is decidable ⋮ Backdoor Sets for CSP. ⋮ Quantified Constraints in Twenty Seventeen ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ The complexity of soft constraint satisfaction ⋮ Efficient interval partitioning-local search collaboration for constraint satisfaction ⋮ On bijunctive predicates over a finite set ⋮ On the CSP Dichotomy Conjecture ⋮ Finding a given number of solutions to a system of fuzzy constraints ⋮ Key (critical) relations preserved by a weak near-unanimity function ⋮ The expressive power of valued constraints: Hierarchies and collapses ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ The expressive power of binary submodular functions ⋮ Combinatorial problems raised from 2-semilattices ⋮ A new tractable class of constraint satisfaction problems ⋮ A polynomial relational class of binary CSP ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Existentially restricted quantified constraint satisfaction ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ On m-Junctive Predicates on a Finite Set ⋮ Tractable combinations of theories via sampling ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ Relatively quantified constraint satisfaction ⋮ TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS ⋮ The existence of a near-unanimity term in a finite algebra is decidable ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ On weak positive predicates over a finite set ⋮ Constraint propagation techniques for the disjunctive scheduling problem ⋮ Recent Results on the Algebraic Approach to the CSP ⋮ Dualities for Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ A quasi-Mal'cev condition with unexpected application. ⋮ The expressive rate of constraints ⋮ Periodic constraint satisfaction problems: Tractable subclasses ⋮ An efficient algorithm for a class of constraint satisfaction problems ⋮ \(H\)-coloring dichotomy revisited
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Network-based heuristics for constraint-satisfaction problems
- An optimal k-consistency algorithm
- Temporal constraint networks
- From local to global consistency
- A generic arc-consistency algorithm and its specializations
- Polynomial interpolation and the Chinese remainder theorem for algebraic systems
- Consistency in networks of relations
- Constraint satisfaction over connected row-convex constraints
- Fast parallel constraint satisfaction
- Decomposing constraint satisfaction problems using database techniques
- Characterising tractable constraints
- Networks of constraints: Fundamental properties and applications to picture processing
- Constraint relaxation may be perfect
- A sufficient condition for backtrack-bounded search
- A Sufficient Condition for Backtrack-Free Search
- On binary constraint problems
- On the minimality and global consistency of row-convex constraint networks
- Closure properties of constraints
- Constraint tightness and looseness versus local and global consistency
- Monotone monadic SNP and constraint satisfaction
- The complexity of satisfiability problems
- A relational model of data for large shared data banks
- Tractable constraints on ordered domains
This page was built for publication: Constraints, consistency and closure
