ACM SIGMOD Anthology TKDE dblp.uni-trier.de

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}
}
BibTeX

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.

Copyright © 1993 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 3, TKDE 1993-1995" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

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) BibTeX
[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) BibTeX
[9]
...
[10]
Jon Doyle: A Truth Maintenance System. Artif. Intell. 12(3): 231-272(1979) BibTeX
[11]
Mark S. Fox, Norman M. Sadeh, Can A. Baykan: Constrained Heuristic Search. IJCAI 1989: 309-315 BibTeX
[12]
Eugene C. Freuder: Synthesizing Constraint Expressions. Commun. ACM 21(11): 958-966(1978) BibTeX
[13]
...
[14]
James W. Goodwin: A Process Theory of Non-monotonic Inference. IJCAI 1985: 185-187 BibTeX
[15]
...
[16]
...
[17]
Robert M. Haralick, Gordon L. Elliott: Increasing Tree Search Efficiency for Constraint Satisfaction Problems. Artif. Intell. 14(3): 263-313(1980) BibTeX
[18]
...
[19]
...
[20]
...
[21]
Alan K. Mackworth: Consistency in Networks of Relations. Artif. Intell. 8(1): 99-118(1977) BibTeX
[22]
...
[23]
...
[24]
Ugo Montanari, Francesca Rossi: Constraint Relaxation may be Perfect. Artif. Intell. 48(2): 143-170(1991) BibTeX
[25]
Bernard Nudel: Consistent-Labeling Problems and Their Algorithms: Expected-Complexities and Theory-Based Heuristics. Artif. Intell. 21(1-2): 135-178(1983) BibTeX
[26]
Bernard Nudel: Solving the General Consistent Labeling (or Constraint Satisfaction) Problem: Two Algorithms and Their Expected Complexities. AAAI 1983: 292-296 BibTeX
[27]
...
[28]
...
[29]
...
[30]
Herbert A. Simon: The Structure of Ill Structured Problems. Artif. Intell. 4(3): 181-201(1973) BibTeX
[31]
...
[32]
...
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
IEEE Transactions on Data and Knowledge Engineering: Copyright © by IEEE,
Joint ACM SIGMOD / IEEE Computer Society Anthology: Copyright © by ACM (info@acm.org) and IEEE, Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:27:51 2009