CSCE 990-06 Advanced Constraint Processing, Spring 2003

Glossary 1 as Homework 1, worth 80 points

Assigned:  Monday, Feb. 3, 2003.
Due:         Monday Feb. 10, 2003.
Note: it would be a good idea to sort the list alphabetically.
  1. A variable is arc-consistent relative to another (binary CSP)
  2. A sub-network of constraints is arc-consistent (binary CSP)
  3. A network of constraints is arc-consistent (binary CSP)
  4. Revise: input, output, what it updates
  5. Two variables are path-consistent relative to a third
  6. A binary constraint Rxi,xj is path-consistent relative to variable xk
  7. A sub-network of 3 variables is path-consistent
  8. A network of constraints is path-consistent.
  9. Revise3: input, output, what it updates
  10. PC-1, PC-3: what they update (according to Dechter)
  11. A path-consistent constraint Rxi,xj
  12. A relation of arity (i-1) is i-consistent relative to a variable
  13. A network is i-consistent
  14. A network is strongly i-consistent
  15. A network is globally consistent
  16. Revise-i: input, output, what it updates
  17. A variable is arc-consistent relative to a non-binary constraint RS
  18. A network of non-binary constraint is arc-consistency
  19. Generalized arc-consistency (GAC): what it updates
  20. Relational arc-consistency: what it updates
  21. Bounds consistency
  22. Global cardinality constraint (check original paper by Regin)
  23. Cumulative constraint
  24. Alldifferent constraint
  25. Sum constraint
  26. Cycle constraint
  27. Global constraint (according to Dechter)
  28. Maximal matching in a bipartite graph
  29. Numeric constraints (according to Dechter)
  30. Boolean constraints (according to Dechter)
  31. Resolution rule
  32. Composition of two binary constraints
  33. Unit clause
  34. A variable  is bounds-consistent relative to a non-binary constraint
  35. A (non-binary) constraint is bounds-consistent
  36. Explain the UNIT-PROPAGATION algorithm
  37. Width of a tree-structured binary CSP
  38. Bi-valued CSP
  39. Conjunctive normal form (CNF)
  40. Horn clause
Do not forget to list your references.


choueiry@cse.unl.edu