A Knowledge Representation for Constraint Satisfaction Problems.

Albert Croker, Vasant Dhar: A Knowledge Representation for Constraint Satisfaction Problems. IEEE Trans. Knowl. Data Eng. 5(5): 740-752(1993)

@article{DBLP:journals/tkde/DharV93,
  author    = {Albert Croker and
               Vasant Dhar},
  title     = {A Knowledge Representation for Constraint Satisfaction Problems},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {5},
  number    = {5},
  year      = {1993},
  pages     = {740-752},
  ee        = {db/journals/tkde/DharV93.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper we present a general representation for problems that can be reduced to constraint satisfaction problems (CSP) and a model for reasoning about their solution. The novel part of the model is a constraint-driven reasoner that manages a set of constraints, specified in terms of arbitrarily complex Boolean expressions and represented in the form of a dependency network. This dependency network incorporates control information (derived from the syntax of the constraints) that is used for constraint propagation, contains dependency information that can be used for explanation and for dependency-directed backtracking, and is incremental in the sense that if the problem specification is modified, a new solution can be derived by modifying the existing solution. The constraint-driven reasoner is coupled to a problem solver which contains information about the problem variables and preference orderings.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 3, TKDE 1993-1995" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An3-3 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

References

[1]: ...
[2]: ...
[3]: ...
[4]: ...
[5]: ...
[6]: ...
[7]: Rina Dechter, Judea Pearl: Network-Based Heuristics for Constraint-Satisfaction Problems. Artif. Intell. 34(1): 1-38(1987)
[8]: Vasant Dhar, Harry E. Pople: Rule-Based versus Structure-Based for Models for Explaining and Generating Expert Behavior. Commun. ACM 30(6): 542-555(1987)
[9]: ...
[10]: Jon Doyle: A Truth Maintenance System. Artif. Intell. 12(3): 231-272(1979)
[11]: Mark S. Fox, Norman M. Sadeh, Can A. Baykan: Constrained Heuristic Search. IJCAI 1989: 309-315
[12]: Eugene C. Freuder: Synthesizing Constraint Expressions. Commun. ACM 21(11): 958-966(1978)
[13]: ...
[14]: James W. Goodwin: A Process Theory of Non-monotonic Inference. IJCAI 1985: 185-187
[15]: ...
[16]: ...
[17]: Robert M. Haralick, Gordon L. Elliott: Increasing Tree Search Efficiency for Constraint Satisfaction Problems. Artif. Intell. 14(3): 263-313(1980)
[18]: ...
[19]: ...
[20]: ...
[21]: Alan K. Mackworth: Consistency in Networks of Relations. Artif. Intell. 8(1): 99-118(1977)
[22]: ...
[23]: ...
[24]: Ugo Montanari, Francesca Rossi: Constraint Relaxation may be Perfect. Artif. Intell. 48(2): 143-170(1991)
[25]: Bernard Nudel: Consistent-Labeling Problems and Their Algorithms: Expected-Complexities and Theory-Based Heuristics. Artif. Intell. 21(1-2): 135-178(1983)
[26]: Bernard Nudel: Solving the General Consistent Labeling (or Constraint Satisfaction) Problem: Two Algorithms and Their Expected Complexities. AAAI 1983: 292-296
[27]: ...
[28]: ...
[29]: ...
[30]: Herbert A. Simon: The Structure of Ill Structured Problems. Artif. Intell. 4(3): 181-201(1973)
[31]: ...
[32]: ...