Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics.
Víctor DalmauPhokion G. KolaitisMoshe Y. VardiPublished in: CP (2002)
Keyphrases
- constraint satisfaction
- bounded treewidth
- monadic datalog
- np complete
- constraint satisfaction problems
- phase transition
- highly parallelizable
- constraint programming
- expressive power
- heuristic search
- decision problems
- constraint relaxation
- conjunctive queries
- relational learning
- boolean functions
- bounded degree
- arc consistency
- constraint propagation
- combinatorial problems
- np hard
- robust fault detection
- russian doll search
- sat solvers
- search algorithm
- forward checking
- relational databases
- satisfiability problem
- soft constraints
- constraint solving
- constraint problems
- information extraction
- query language
- computational complexity