A Short Bibliography on Search  
		  and Constraint-Satisfaction

                --------------------------------
Path: yunexus!utzoo!mnetor!uunet!lll-winken!lll-tis!ames!umd5!purdue!decwrl!
+ ucbvax!ADS.COM!rshu%meridian
From: rshu%meridian@ADS.COM (Richard Shu)
Newsgroups: comp.ai.digest
Subject: Search bibliography
Message-ID: <8804140029.AA19540@ads.com>
Date: 14 Apr 88 00:18:22 GMT
Lines: 281
 
BACHANT, J. AND McDERMOTT, J.  R1 revisited: four years in the trenches.
AI Magazine 5#3 (1984).
 
BANNERJI, R.B.   A comarison of three problem solving methods. Proc 5th IJCAI
(1977), 442ff.
 
BANNERJI, R.B. AND ERNST, C.W.   A theory for the complete mechanization of
a GPS-type problem solver. Proc 5th IJCAI (1977), 450ff.
 
BARNETT, J.A.   How much is control knowledge worth? a primitive
example. Artif Intel 22 (1984), 77-89.
 
BARTON, G.E.   A multiple-context equality-based reasoning system.
AI Lab TR-715, MIT (1983).
 
BENOIT, J.W.   A use of ATMS in hierarchical planning.  Proc DARPA Knowledge
Based Planning Workshop, Austin TX (Dec 1987).
 
BERLINER, H.A.   Search vs. knowledge: an analysis from the domain of games.
Tech Report CMU-CS-82-104, Department of Computer Science, Carnegie-Mellon
University. { search reduction vs goal recognition }
 
BOBROW, D.G. AND WEGBREIT, B.   A model and stack implementation of multiple
environments. Comm ACM 16 (1973), 591-603.
 
BORNING, A.   ThingLab -- an object-oriented system for building simulations
using constraints. Proc 5th IJCAI (1977), 497-498.
 
BOTVINNIK, M.M.   Decision making and computers. Computer Chess 3 (198X), 169ff.
 
CHURCH, K.W.   Coordinate squares: a solution to many chess pawn endgames.
Proc 6th IJCAI (1979), 149ff. { back-tracking, knowl util, frame problem }
 
DAVIS, M.   The mathematics of non-monotonic reasoning. Artificial
Intelligence 13 (1980), 73ff.
 
DECHTER, R.   Learning while searching in constraint-satisfaction problems.
Proc AAAI (1986), 178ff.
 
DECHTER, R. AND PEARL, J.   Network-based heuristics for constraint
satisfaction problems. Artif Intel 34 (1988), 1ff.
 
DeKLEER, J., DOYLE, J., STEELE, G.L. AND SUSSMAN, G.J.   AMORD: explicit
control of reasoning. SIGART Newsletter 64 (Aug 1977), 116-125.
 
DeKLEER, J., DOYLE, J., STEELE, G.L.Jr. AND SUSSMAN, G.J.   Explicit control
of reasoning. ACM SIGPLAN Notices Vol 12, Proc Symp on Artificial Intelligence
and Programming Languages (Aug 1977), 116ff.
 
DeKLEER, J., DOYLE, J., RICH, C., STEELE, G.L.Jr. AND SUSSMAN, G.J.  AMORD, a
deductive procedure system. MIT AI Memo 435 (Jan 1978).
 
DeKLEER, J. AND SUSSMAN, G.J.   Propagation of constraints applied
to circuit synthesis. Circuit Theory and Applications 8 (1980).
 
DeKLEER, J.   Choices without backtracking. Proc AAAI (1984).
 
DeKLEER, J.   An assumption-based TMS.  Artif Intel 28 (1986), 127ff.
 
DeKLEER, J.   Extending the ATMS. Artif Intel 28 (1986), 163ff.
 
DeKLEER, J.   Problem solving with the ATMS. Artif Intel 28 (1986), 197ff.
 
DeKLEER, J. AND WILLIAMS, B.C.   Back to backtracking: controlling the ATMS.
Proc AAAI (1986), 910ff.
 
DHAR, V.   An approach to dependency directed backtracking using domain
specific knowledge. Proc 9th IJCAI (1985), 188ff.
 
DOYLE, J.   Truth maintenance systems for problem solving. Proc 5th IJCAI
(1977), 247.
 
DOYLE, J.   Truth maintenance systems for problem solving. Tech Rept
419, AI Lab, MIT (Jan 1978).
 
DOYLE, J.   A glimpse of truth maintenance. Proc 6th IJCAI (1979), 232ff.
 
DOYLE, J.   A truth maintenance system. Artificial Intelligence 12 (1979),
231ff.
 
DOYLE, J. AND LONDON, P.   A selected descriptor-indexed bibliography to the
literature on belief revision. Memo 568, AI Lab, MIT (1980).
 
DOYLE, J.   Methodological simplicity in expert system construction -- the
case of judgments and reasoned assumptions. Tech Rept CMU-CS-83-114, Dept
of CS, CMU (1983).
 
EAVARONE, D. AND ERNST, G.    A program that generates good
difference orderings and tables of connections for GPS. Proc IEEE
Systems Science and Cybernetics Conf, Pittsburgh, PA (Oct 1970), 226ff.
 
ERNST, G.    Sufficient conditions for the success of GPS. J ACM 16
(Oct 1969), 517ff.
 
FEIGENBAUM, E.A.   The art of artificial intelligence: 1. themes and case
studies of knowledge engineering. Proc 5th IJCAI (1977), 1014ff. { generate &
test in expert systems }
 
FOX, M.S.   Constraint-directed search: a case study of job-shop
scheduling. PhD thesis, Rept CMU-CS-83-161, Carnegie Mellon Univ
(Dec 1983).
 
FOX, M.S., ALLEN, B. AND STROHM, G.   Job-shop scheduling: an
investigation of constraint-directed reasoning. Proc AAAI (1982), 155ff.
 
GASCHNIG, J.   A general backtrack algorithm that eliminates most redundant
tests. Proc 5th IJCAI (1977), 457ff.
 
HARALICK, R.M. AND ELLIOTT, G.L.   Increasing tree search efficiency
for constraint satisfaction problems. Proc 6th IJCAI (1979), 356ff.
 
HARRIS, D.   A hybrid structured-object and constraint representation
language. Proc AAAI (1986), 986ff.
 
HAYES, P.J.  A representation for robot plans. Proc 4th IJCAI (1975).
 
HEWITT, C.   How to use what you know. Proc 4th IJCAI (1975), 189ff.
 
KASIF, S.   On the parallel complexity of some constraint satisfaction
problems. Proc AAAI (1986), 349ff.
 
KELLY, V.  The CRITTER system: automated critiquing of digital hardware
designs. TR WP-13, AI/VLSI project, Rutgers (1983). Also in Proc Design
Automation Conf (1984).
 
KELLY, V.  The CRITTER system: an AI approach to digital circuit design
critiquing. PhD thesis, Rutgers University, New Brunswick, NJ (Jan 1985).
 
KIBLER, D. AND MORRIS, P.   Don't be stupid. Proc 7th IJCAI (1981), 345ff.
{ use of negative heuristics (checks?) }
 
KLINE, P.  The superiority of relative criteria in partial matching and
generalization. Proc 7th IJCAI (1981).
 
KORNFELD, W.A.   The use of parallelism to implement a heuristic
search. Proc 7th IJCAI (1981), 575ff.
 
LAIRD, J.E. AND NEWELL, A.   A universal weak method. TR 83-141, Dept of
Computer Science, CMU (1983).
 
LAIRD, J.E. AND NEWELL, A.   A universal weak method: summary of results.
Proc 8th IJCAI (1983).
 
LAIRD, J.E.   Universal subgoaling. PhD thesis, Dept of Computer Science,
CMU (1983).
 
LONDON, P.   A dependency-based modelling mechanism for problem solving.
TR-589, Dept of CS, U of Maryland, College Park (Sep 1978).
 
LONDON, P.   Dependency networks as a representation for modelling in
general problem solvers. PhD thesis, Tech Rept 698, Dept of CS, U of
Maryland at College Park (1978).
 
MACKWORTH, A.K.   Consistency in networks of relations.
Artificial Intelligence 8 (1977), 99ff.
 
MARTINS, J.P. AND SHAPIRO, S.C.   Reasoning in multiple belief
spaces. Proc 8th IJCAI (1983).
 
MATWIN, S. AND PIETRZYKOWSKI, T.  Intelligent backtracking in plan-based
deduction. IEEE Trans PAMI 7 #6 (Nov 1985), 682ff.
 
MATWIN, S. AND PIETRZYKOWSKI, T.  Exponential improvement of efficient
backtracking: a strategy for plan-based deduction. Proc 7th Conf on Auto
Deduction.
 
McALLESTER, D.A.   A three-valued truth maintenance system. MIT Artificial
Intelligence Laboratory, Memo 473 (1978).
 
McALLESTER, D.   An outlook on truth maintenance. AI Lab Memo 551, MIT (1980).
 
McALLESTER, D.   Reasoning Utility Package users' manual. AIM-667, AI Lab,
MIT (1982).
 
McDERMOTT, D.   Contexts and data dependencies: a synthesis. IEEE Trans PAMI
5/3 (1983), 237ff.
 
MITTAL, S. AND FRAYMAN, F. Making partial choices in contraint reasoning
problems. Proc AAAI (1987), 631ff.
 
MORRIS, P.H. AND NADO, R.   Representing actions with an ATMS. Proc AAAI
(1986), 13ff.
 
NEVINS, A.J.   A human-oriented logic for automatic theorem proving.
J ACM 21 (1974), 606ff. { case analysis }
 
O'RORKE, P.  Constraint posting and propagation in explanation-based
learning. Working Paper 70, AI Group, Coordinated Science Lab, U of Illinois
at Urbana-Champaign (1986).
 
PIETRZYKOWSKI, T. AND MATWIN, S.   Exponential improvement of exhaustive
backtracking: data structure and implementation. Proc 7th Conf on Auto
Deduction.
 
POST, E.L.    Formal reductions of the general combinatorial decision
problem. Amer J of Mathematics 65 (1943), 197ff.
 
PURDOM, P.W.Jr.   Solving satisfiability with less searching. IEEE Trans
PAMI 6 #4 (July 1984), 510ff.
 
RIVEST, R.   On self-organizing sequential search heuristics. CACM 19/2
(1976), 63ff.
 
SEIDEL, R.   A new method for solving constraint satisfaction problems.
Proc 7th IJCAI (1981), 338ff.
 
SMITH, R.G.   Applications of the contract net: search. Proc 3rd
CSCSI Conf (May 1980).
 
STALLMAN, R.M. AND SUSSMAN, G.J.   Forward reasoning and dependency-directed
backtracking in a system for computer-aided circuit analysis. Artificial
Intelligence 9 (1978), 135ff.
 
STEELE, G.L.   The definition and implementation of a computer
programming language based on constraints. AI Lab TR-595, MIT (1979).
 
STEINBERG, L.I.   Design as refinement plus constraint propagation: the VEXED
experience. Proc AAAI (1987), 830ff.
 
SUSSMAN, G.J. AND STALLMAN, R.M.   Heuristic techniques in computer-aided
circuit analysis. IEEE Trans Circuits & Systems CAS-22 (Nov 1975).
 
SUSSMAN, G.J.   SLICES: at the boundary between analysis and synthesis.
Memo 433, AI Lab, MIT (July 1977).
 
SUSSMAN, G.J. AND STEELE, G.L.   CONSTRAINTS: a language for
expressing almost-hierarchical descriptions. Artif Intel 14 (1980).
 
WILLIAMS, C.   ART - the advanced reasoning tool - conceptual
overview. Inference Corp (1984).
 
Foo, Norman Y., & Anand S. Rao (1987) "Open world and closed world
negations," Report RC 13122, IBM T. J. Watson Research Center.
 
Foo, Norman Y., & Anand S. Rao (in preparation) "Semantics of
dynamic belief systems."
 
Foo, Norman Y., & Anand S. Rao (in preparation) "Belief and ontology
revision in a microworld.
 
Rao, Anand S., & Norman Y. Foo (1987) "Evolving knowledge and logical
omniscience," Report RC 13155, IBM T. J. Watson Research Center.
 
Rao, Anand S., & Norman Y. Foo (1987) "Evolving knowledge and
autoepistemic reasoning," Report RC 13155, IBM T. J. Watson Research
Center.
 
Rao, Anand S., & Norman Y. Foo (1986) "Modal horn graph resolution,"
Proceedings of the First Australian AI Congress, Melbourne.
 
Rao, Anand S., & Norman Y. Foo (1986) "DYNABELS -- A dynamic belief
revision system," Report 301, Basser Dept. of Computer Science,
University of Sydney.
 
Sowa, John F. (1984) Conceptual Structures:  Information Processing in
Mind and Machine, Addison-Wesley, Reading, MA.
 
Way, Eileen C. (1987) Dynamic Type Hierarchies:  An Approach to
Knowledge Representation through Metaphor, PhD dissertation,
Systems Science Dept., SUNY at Binghamton.
 
 
For copies of the IBM reports, write to Distribution Services 73-F11;
IBM T. J. Watson Research Center; P.O. Box 218; Yorktown Heights,
NY 10598.
 
For the report from Sydney, write to Basser Dept. of Computer Science;
University of Sydney; Sydney, NSW 2006; Australia.
 
For the dissertation by Eileen Way, write to her at the Department
of Philosophy; State University of New York; Binghamton, NY 13901.
 
 
 
Richard Shu
RSHU@ADS.COM