\documentstyle{article} \input{vijay-macros} \def\explains{\withmath{\mathrel{\mid\vdash}}} \def\w{\mbox{$\wedge~$}} \def\ab{\mbox{$\; \Rightarrow \;$}} \newcommand{\triple}[1]{\mbox{$ \langle #1, \Delta \rangle$}} \title{ {\Large {\bf Abduction in Concurrent Constraint Programming}}} \author{ Philippe Codognet\\ {\em INRIA-Rocquencourt} \\ {\em Domaine de Voluceau} \\ {\em 78153 Le Chesnay}, \\ {\em FRANCE}\\ {\tt Philippe.Codognet@inria.fr} \and Vijay Saraswat\\ {\em Xerox PARC} \\ {\em 3333 Coyote Hill Road} \\ {\em Palo Alto, CA 94304}, \\ {\em U.S.A.} \\ {\tt saraswat@parc.xerox.com}} \date{March 1992} \begin{document} \maketitle \noindent\noindent {\bf Topic Area :} Reasoning methods (deduction, abduction, constraint solving, belief revision) \newpage \section{Introduction} Abduction was introduced by Pierce \cite{Pierce33} as a new inference mechanism for logical systems along with deduction and induction. It has been used in various domains such as semiotics \cite{Eco84}, linguistics \cite{Hobbs-Stickel88}, and in Artificial Intelligence, since \cite{Pople73}, mainly in the perspective of diagnosis reasoning \cite{Cox86} \cite{Poole88} \cite{Dekleer87}.\footnote{[more on abduction in AI (Poole,...)]} Abduction has also been introduced in Logic Programming by \cite{Kow88}, and then further developed in \cite{Eshghi89} \cite{Kakas90} \cite{Kakas91}. Although Constraint Logic Programming (CLP) languages have been introduced for some years \cite{Jaffar-lassez87} and generalize in an obvious way Logic Programming, no attempt have been made to extend abduction to such a framework, in spite of numerous analogies existing between abduction and constraint processing. Indeed both systems are intended to deal with partial information and to avoid floundering when dealing with under-specified problems, both in fact conjecture relations between unknowns instead of getting stuck in a ``dead-end'' when complete characterization is missing. This correspondence is stressed in that the basic step of an abduction process consist in adding an abducible literal to the current set of hypotheses as long as it is consistent with it, while the basic step of constraint solving consists in adding a new constraint to the current set of constraint and checking consistency. Our work is intented to propose a notion of abduction for CLP languages, and more precisely for the family of Concurrent Constraint ({\tt cc}) languages proposed by \cite{Sar89} \cite{Sar90}, which extend CLP languages with concurrency features that have emerged from the domain of Concurrent Logic Programming. The key idea underlying the \cc{} framework is to use constraints to extend the synchronization and control mechanisms of concurrent logic languages. Briefly, multiple agents (processes) run concurrently and interact by means of a shared {\em store}, i.e.{} a global set of constraints. Each agent can either add a new constraint to the store ({\em Tell} operation) or check wether or not the store entails a given constraint ({\em Ask} operation). Synchronization is achieved through a {\em blocking ask} : an asking agent may block and suspend if one cannot state if the asked constraint is entailed nor its negation is entailed. Thus nothing prevents the constraint to be entailed, but the store does not yet contain enough information. The agent is suspended until other concurrently running agents add ({\it Tell}) new constraints to the store to make it strong enough to decide. The denotational semantics of \cc{} languages \cite{SRP91} consists in interpreting the basic operations in \cc{} languages and the agents as {\it closure operators} over the underlying constraint system \footnote{A closure operator $f$ over a lattice $(L, \leq)$ is a unary function that is monotone (i.e., $f(x) \geq f(y)$ whenever $x \geq y$), idempotent (i.e., $f(f(x))=f(x)$) and extensive (i.e., $f(x) \geq x$).}. A constraint system is a pair $(D,\vdash)$ where $D$ is the constraint domain and $\vdash$ an entailment relation over $D$ satisfying some simple conditions, \cite{SRP91}. In this framework, abduction consists, given a constraint $c$, an agent $a$ and a store $s$, to find a minimal {\it explanation} $d$ of $c$, that is a constraint $d$ such that $a(s \cup d) ~ \vdash ~ c$. This means that we want to find the minimal extension ($d$) of the current store $s$ so that, running the agent $a$ in the store $s \cup d$, we could derive something equal or stronger than $c$, i.e.{} something with ``at least as much information'' as $c$. In general, $a$ and $s$ are given beforehand, and this scheme can be used for diagnosis reasoning as follows : the definition of the agent $a$ is a program describing some artifact, $s$ represent some internal integrity constraints. Then the constraint $c$ represent some observation, and the explanation $d$ corresponds thus to the ``causes'' of $c$ given $a$, that is the constraint corresponding to the behavior hypotheses that that are necessary to derive an output constraint at least as strong as $c$ (the observation). So what could be the operational behavior of such an abduction mechanism in the \cc{} framework ? Intuitively, considering that abduction in deductive systems is a mean to generate hypotheses allowing the deduction process to continue when normally a ``dead-end'' is reached (cf.{} \cite{Cox86}), then by analogy abduction in \cc{} languages should allow the computation to continue when a ``deadlock'' is reached, i.e.{} when all agents are suspended on some {\it ask} operations. Thus abduction has to generate some hypothetical constraints that would lead some ask operations to be satisfied and thus resume some agents in order to let the computation proceed again. Hence the abduction mechanism is intended to ``abduce'' the minimal input needed for an agent to resume and generate some new output. This scheme thus abduce ask operations upon which some agents are pending, telling then the ``asked contraints'' to some hypothetical sub-store. The paper is organized as follows. Section~2 briefly presents the basic definitions of constraint systems and concurrent constraint ({\tt cc}) languages. Section~3 introduces the concept of abduction in such a framework, and define the notion of explanation and minimal explanation. Section~4 then relates it to the operational behavior of \cc{} languages, in order to give a concrete abduction procedure, whose equivalence w.r.t.{} the declarative notion is shown. In Section~5, we dicuss the problem of controlling such an abductive process, i.e.{} of controlling the generation of hypotheses. Section~6 proposes a simple application to diagnosis reasoning, and a short comparison with previous work on abduction is conducted in Section~7, followed by a short conclusion. \section{\cc{} languages} \footnote{[Brief definitions of constraint systems, syntax and a few words on semantics of (determinate?) cc languages]} The syntax of the non-determinate \cc{} languages is very simple: \begin{equation} \begin{array}{rlll} \mbox{{\em Programs}}& P \;{::=} & H {::} A \alt P . P \\ \mbox{{\em Agents}}& A \; {::=} & \;\; c & \mbox{(Tell)} \\ & & \alt c \rightarrow A & \mbox{(Ask)} \\ & & \alt A, A & \mbox{(Conjunction)} \\ & & \alt A ; A & \mbox{(Disjunction)} \\ & & \alt \exists X A & \mbox{(Local variables)} \\ & & \alt H & \mbox{(Procedure Call)} \\ \mbox{{\em Procedure Call}} & H \; {::=} & p(X_1,\ldots, X_n) \end{array} \end{equation} Programs are just sequences of definitions, associating an atomic formula with an {\em agent}. An agent is either a primitive constriant, a simple conditional (ask) agent, an {\em abducible} ask agent, a conjunction (parallel composition), disjunction (backtracking search), existential quantification (local hiding), or atomic formula (procedure call). We now discuss the operational semantics of \cc{} languages. Configurations are pairs of the form \tuple{\Gamma, s} where $s$ is a set of constraints, and $\Gamma$ is a multiset of agents. (The empty multiset is denoted $()$.) Below, we define a binary relation $\derives$, the {\em transition} relation which specifies how configurations evolve. Note that only {\em fair} execution sequences (e.s.) are considered legal. (A fair e.s.{} is not unfair; an {\em unfair} e.s.{} is one in which some given transition is enabled at every configuration in the sequence, and never taken.) We omit the rules for existential quantification, backtracking and procedure calls, since they are standard. (See for example, \cite{angelic-nondet}.) Below, $\vdash$ is the entailment relation of the underlying constraint system. \begin{equation} \begin{array}{l} \axname{Tell}\axiom{\tuple{(\Gamma, c), s} \derives \tuple{\Gamma, s\cup\{c\}}}\\ \rname{Ask}\from{s \vdash d}% \infer{\tuple{(\Gamma, d \then A), s} \derives \tuple{(\Gamma,A),s}}\\ \axname{Parallel Composition}\axiom{\tuple{(\Gamma, (A_1,A_2)), s} \derives \tuple{(\Gamma,A_1,A_2), s}} \end{array} \end{equation} \section{Abduction in \cc{} languages} %% Vijay addition begin. \begin{definition} Let $SD:L \rightarrow L$ be a closure operator, and $b,r \in L$ be constraints. A constraint $e \in L$ is an {\em explanation} for $r$ given $b$, if $SD(b\wedge e) \geq r$. We shall write $e \explains_{f,b} r$, and just $e \explains r$, when $f$ and $b$ are clear from the context. An explanation is {\em minimal}, if, in addition, for any other explanation $e'$ $e'=e$ whenever $e' \leq e$. \end{definition} Thus an explanation is an input which can explain the result (via the given the inference rules $SD$). A minimal explanation, is one which makes just as many assumptions as needed to obtain an explanation. In the following, when $SD$ and $b$ are fixed, we shall just say that $e$ explains $r$. Clearly, there may be more than one explanation for a system $(SD,b,r)$. In addition we have: \begin{proposition} Assume $SD$ and $b$ are fixed. \begin{itemize} \item $d \explains r_1$ and $d \explains r_2$ implies $d \explains c_1 \wedge c_2$ \item $d \explains c$ and $c \explains e$ implies $d \explains e$ \end{itemize} \end{proposition} %% Definition of normal form. \section{An operational abduction procedure} %% Abduction on deadlock, proof that we thus compute (minimal) explanations. In Abductive \cc{} languages we add the syntactic production: \begin{equation} \begin{array}{rlll} \mbox{{\em Agents}}& A \; {::=} & c \ab A & \mbox{(Abducible Ask)} \\ \end{array} \end{equation} The operational semantics of the abductive \cc{} language is shown in Table~\ref{ab-trans-sem}. \begin{table} \begin{tabular}{|l|} \hline \begin{minipage}[t]{\columnwidth} Configurations are now triples of the form \tuple{\Gamma, s, \Delta} where $\Delta$ is a set of (abduced) constraints, $s$ is a set of constraints, and $\Gamma$ is a multiset of agents. \paragraph{Basic Ask-and-Tell language.} $$\begin{array}{rll} \mbox{(Tell)} & \triple{(\Gamma, c), s} \derives \triple{\Gamma, s\cup\{c\}}\\ \mbox{(Ask)} &\triple{(\Gamma, d \then A), s} \derives \triple{(\Gamma,A),s} & s \vdash d\\ \mbox{(Parallel Composition)} & \triple{(\Gamma, (A_1,A_2)), s} \derives \triple{(\Gamma,A_1,A_2), s}\\ \end{array}$$ \paragraph{Abduction.} $$\begin{array}{rll} \mbox{(Abductive Ask 1)} & \tuple{(\Gamma,d \ab A),s, \Delta} \derives \tuple{(\Gamma,A),s, \Delta} & s\cup\Delta \vdash d \\ \mbox{(Abductive Ask 2)} & \tuple{(\Gamma,d \ab A),s, \Delta} \derives \tuple{(\Gamma,A),s,\Delta\cup\{d\}} & s\cup\Delta \not\vdash d \\ \end{array}$$ \end{minipage}\\ \hline\end{tabular} \caption{Transition system for abductive \cc{} language}\label{ab-trans-sem} \end{table} \section{Controlling abduction} In order to be truly usable, hypothetical reasoning systems need adequate strategies for focusing the generation of hypotheses to useful parts of the search space and avoiding combinatorial explosion. This problem is crucial in Assumption-based sytems (e.g. ATMS), see \cite{atms-focus} \cite{focus} for such a discussion. More generally, this means that the abduction process has to be controlled in order to minimize abduction. Also it is important, as soon as some constraint has been abduced, to immediately resume deductions that use it in order to confirm or deny the hypothesis as quickly as possible. This amounts to a full hypothetico-deductive system in the spirit of \cite{evans91}. In our framework, we can take advantage of the genuine concurrency of the model, to achieve such a behavior. All agents with aks pending on some abducible constraint (i.e. whose action is dependant of this hypothesis) will be woken up as soon as the constraint will be abduced and added to the store. \\ To control abduction and achieve a lazy hypothesis formation policy, we can also take advantage of research on concurrent logic languages, such as the {\em Andorra principle}. The Andorra principle was proposed by D.H.D. Warren \cite{warren-andorra} in order to combine Or- and And-parallel execution of logic programs, and it has now bred a variety of idioms and extensions developed by different research groups, among which Andorra-I \cite{CostaWY91b} and Andorra Kernel Language\cite{JansonHSLP91}. The essential idea is to execute determinate goals first and concurrently, delaying thus the execution of non-determinate goals until no determinate goal can proceed any more. The roots of such a concept can be traced back further to the early developments of Prolog, as for instance in the {\em sidetracking} search procedure of \cite{Pereira-Porto79} which favors the development of goals with the least alternatives (and hence determinate goals as a special case). This is indeed but another instance of the old ``first fail'' heuristic often used in AI. Applying such ideas to the abduction scheme, one could design a strategy that would delay abduction as long as normal (deductive) computation can execute. Abduction takes place only when normal computation reaches a deadlock and cannot proceed anymore without additional (hypothetical) information. Moreover, as soon as a constraint is abduced, i.e. added to the store, normal computation can resume following the usual \cc{} operational semantics, until a new deadlock is reached and more hypothesis are demanded. Focused search is thus very easily and smoothly integrated in the usual \cc{} operational behavior, thanks to the concurrent execution mechanism and a simple variant of the Andorra principle. \section{Application to diagnosis reasoning} Our main application topic is diagnosis reasoning, and especially fault diagnosis, as most abductive systems in AI. In that direction it looks very interesting to investigate constraints over finite domains, as proposed by the CHIP constraint language \cite{pvh89}. Finite domains nicely fits into the \cc{} framework, as shown by the {\tt cc(FD)} language presented in \cite{cc-fd}. We believe that such a language is well suited for diagnosis reasoning for two main reasons. First, because diagnosis problems hypotheses typically concern the faulty state of some components, and the set of all such possible state is in general (hopefully) finite. Second, because very efficient constraint solving algorithms exist for that domain, and we could thus hope to have an efficient diagnosis reasoner. \paragraph{The three bulbs example.} Let us now now describle a simple fault diagnosis problem and its formulation in {\tt cc(FD)}. This example is rephrased from \cite{Str89} and deals with a simple electrical circuit consisting of three bulbs connected in parallel to a battery by wires. Observation shows that only the third bulb is lit and an explanation of this phenomenon is sought. \begin{ccprogram} \agent battery(Mode,Left,Right) :: Mode=empty \ab (Left=0, Right=0), Mode=ok \ab (Left=plus, Right=plus).. \agent wire(State,In,Out) :: State=ok \ab In=Out, State=broken \ab Out=0.. \agent bulb(State,Light,Left,Right) :: State=ok \ab \R(Left=plus, Right=plus \then Light=on), (Left=0 \then Light=off), (Right=0 \then Light=off)\L, State=damaged \ab Light=off.. \agent circuit(S,B1,B2,B3,W1,W2,W3,W4,W5,W6,L1,L2,L3) :: battery(S,Sl,Sr), wire(W1,Sl,B1l), wire(W2,Sr,B1r), bulb(B1,L1,B1l,B1r), wire(W3,B1l,B2l), wire(W4,B1r,B2r), bulb(B2,L2,B2l,B2r), wire(W5,B2l,B3l), wire(W6,B2r,B3r), bulb(B3,L3,B3l,B3r).. \end{ccprogram} With the predicate {\tt q/1} defined by: \begin{ccprogram} \agent q :: L = [s-S,b1-B1,b2-B2,b3-B3,w1-W1,w2-W2,w3-W3,w4-W4,w5-W5,w6-W6], abduce\(circuit([S,B1,B2,B3,W1,W2,W3,W4,W5,W6], O1, O2, O3), L, (O1=off,O2=off, O3=on)\).. \end{ccprogram} we obtain the interaction: {\footnotesize \begin{verbatim} | ?- q. Explanation: b3=ok,w6=ok,w5=ok,b2=damaged,w4=ok,w3=ok,b1=damaged,w2=ok,w1=ok,s=ok,true. yes | ?- \end{verbatim} } \paragraph{Combinational circuits.} More generally, it is possible to give system descriptions of combinatorial digital circuits in a straightforward way, in \cc{} languages. In abductive \cc{} it is possible to obtain abductive diagnoses in a straightforward way. \begin{ccprogram} \agent gate(Id, Type, In1, In2, Out) :: (Id=ok \ab table(Type, In1, In2, Out)), (Id=stuck\_at\_0 \ab Out = 0), (Id=stuck\_at\_1 \ab Out = 1).. \agent table(and, I1, I2, O) :: (I1 =0, I2=0 \then O=0), (I1 =0, I2=1 \then O=0), (I1 =1, I2=0 \then O=0), (I1 =1, I2=1 \then O=1).. \agent table(or, I1, I2, O) :: (I1 =0, I2=0 \then O=0), (I1 =0, I2=1 \then O=1), (I1 =1, I2=0 \then O=1), (I1 =1, I2=1 \then O=1).. \agent table(xor, I1, I2, O) :: (I1 =0, I2=0 \then O=0), (I1 =0, I2=1 \then O=1), (I1 =1, I2=0 \then O=1), (I1 =1, I2=1 \then O=0).. \agent adder([Sx1,Sa1,Sx2,Sa2,So], In1,In2,In3,Out1,Out2) :: gate(Sx1, xor, In1, In2, X1), gate(Sa1, and, In1, In2, A1), gate(Sx2, xor, X1, In3, Out1), gate(Sa2, and, In3, X1, A2), gate(So, or, A1, A2, Out2).. \end{ccprogram} With the predicate {\tt q/1} defined by: \begin{ccprogram} \agent q :: L = [sx1-Sx1, sa1-Sa1, sx2-Sx2, sa2-Sa2, so1-So1], Modes = [Sx1, Sa1, Sx2, Sa2, So1], abduce\((adder(Modes, 0, 1, 0, Out1, Out2), adder(Modes, 1, 1, 1, Out3, Out4)), L, (Out1 = 0, Out2 = 0, Out3 = 1, Out4 = 1)\).. \end{ccprogram} we obtain the interaction: {\footnotesize \begin{verbatim} | ?- q(A). Explanation: so1=ok,sa2=ok,sx2=ok,sa1=ok,sx1=stuck_at_0,true. yes | ?- \end{verbatim} } \section{Relations with other approaches}\footnote{[More on AI approaches (Poole, ...)]} As ask operations corresponds to a simple form of intuitionistic implication \cite{cc-logic}, our abduction scheme relates to a system of hypothetical reasoning with implicative clauses such as \cite{N-prolog}. Also remark that constraints are abducibles and not agents, which could seem quite away from the original paradigm of abduction in logic programs \cite{Kow88} where predicates are abducibles. However Kowalski's scheme can be easily rephrased in our framework : it corresponds to the special case of the {\tt Herbrand} constraint system, that is, in the traditional view of constraints as first-order formulas with domain-specific interpretations \cite{Jaffar-lassez87} \cite{Sar89}, the constraint system where constraints are interpreted in their free algebra. Moreover the notion of ``integrity constraints'' in that scheme then straightforwardly correspond to have some initial set of constraints in our framework. A scheme for integrating \cc{} languages and hypothetical reasoning has already been proposed in \cite{cc-atms} which integrates ATMS-based techniques in the \cc{} approach. The main difference is its {\it explicit} handling of the assumptions underlying a constraint (in the ATMS manner), while our approach mainly deals with an {\it implicit} handling of assumptions. Assumptions are also limited in \cite{cc-atms} to boolean constraints (as in the traditional ATMS), while any constraint domain can be used in the new scheme. \section{Conclusion} We have presented a general scheme for abduction in concurrent constraint (\cc{}) languages, which truely relates abduction and constraint solving. Thanks to the generality of \cc{} languages, it emcompass both logic languages and CLP languages as particular instances. This approach can be smoothly integrated into the denotational semantics of \cc{} languages. For control issues the genuine concurrency of the model, coupled with a variant of the Andorra principle for delaying abduction as long as normal (deductive) computation can proceed, are sufficient to provide a focused behavior and a lazy hypothesis formation policy. \paragraph{Acknowledgements.} \newpage {\footnotesize \bibliographystyle{plain} \begin{thebibliography}{99} \bibitem{Pierce33} Charles S. Pierce. {\em collected papers}. Cambridge University Press, 1933. \bibitem{Eco84} Umberto Eco. {\em Semiotics and philosophy of language}. 1984 \bibitem{Hobbs-Stickel88} J. Hobbs, M. Stikel, P. Martin and D. Edwards. Interpretation as abduction. In {\em proceedings of the 26th Annual Meeting, Association for Computational Linguistics}, Buffalo, USA, 1988. \bibitem{Pople73} H. E. Pople Jr. \newblock On the mechanization of abductive logic. \newblock In {\em proceedings of IJCAI 73}, 1973. \bibitem{Cox86} P. T. Cox and T. Pietrzykowski. \newblock {Causes for events : their computation and application}. \newblock In {\em proceedings of the 8th Conference on Automated Deduction}, LNCS 230, Springer Verlag 1986. \bibitem{Poole88} D. Poole. Explanation and prediction: an architecture for default and abductive reasoning. {\em Canadian Computational Intelligence Journal}, vol. 5 (2), 1989. \bibitem{Dekleer87} Raymond Reiter and Johan de~Kleer. \newblock Foundations of assumption-based truth maintenance systems: a preliminary report. \newblock In {\em Proceedings of AAAI-87}, pages 183 -- 188, August 1987. \bibitem{Kow88} K. Eshghi and R. A. Kowalski. \newblock Abduction through Deduction. \newblock Research report, Imperial college, March 1988. \bibitem{Eshghi89} K. Eshghi and R. A. Kowalski. \newblock Abduction compared with negation as failure. \newblock In {\em proceedings ICLP 89}, Lisbon, Portugal, MIT Press 1989. \bibitem{Kakas90} A. C. Kakas and P. Mancarella. \newblock Generalized stable models : a semantics for abduction. \newblock In {\em proceedings of ECAI 90}, Stockholm, Sweden, 1990. \bibitem{Kakas91} A. C. Kakas and P. Mancarella. \newblock On the relation between truth maintenance and abduction. \newblock In {\em proceedings of PRICAI 90}, Nagoya, Japan, 1990. \bibitem{Jaffar-lassez87} J.~Jaffar and J-L. Lassez. \newblock {Constraint Logic Programming}. \newblock In {\em {POPL-87}}, Munich, FRG, January 1987. \bibitem{Shapiro89} E.~Shapiro. \newblock The family of concurrent logic programming languages. \newblock {\em {ACM} computing surveys}, 21(3), september 1989. \bibitem{cc-logic} Patrick Lincoln and Vijay Saraswat. \newblock {P}roofs as {C}oncurrent {P}rocesses: {A} {L}ogical {I}nterpretation for {C}oncurrent {C}onstraint {P}rogramming. \newblock Technical report, Systems Sciences Laboratory, Xerox PARC, November 1991. \bibitem{angelic-nondet} R.~Jagadeesan, V.~Shanbhogue, and V.~Saraswat. \newblock Angelic non-determinism in concurrent constraint programming. \newblock Technical report, System Sciences Laboratory, Xerox PARC, January 1991. \bibitem{Sar89} V.A. Saraswat. \newblock {\em {Concurrent Constraint Programming Languages}}. \newblock PhD thesis, Carnegie-Mellon University, 1989. \bibitem{Sar90} V.A. Saraswat and M.~Rinard. \newblock {Concurrent Constraint Programming}. \newblock In {\em {Proceedings of Seventeenth ACM Symposium on Principles of Programming Languages}}, San Francisco, CA, January 1990. \bibitem{SRP91} V.A. Saraswat, M.~Rinard, and P.~Panangaden. \newblock {Semantic Foundations of Concurrent Constraint Programming}. \newblock In {\em {Proceedings of Ninth ACM Symposium on Principles of Programming Languages}}, Orlando, FL, January 1991. \bibitem{N-prolog} D. M. Gabbay. \newblock N-Prolog : an extension of Prolog with hypothetical implication. \newblock {\em Journal of Logic Programming}, vol. 1 (4) 1984 and vol. 2 (4) 1985. \bibitem{cc-atms} V. Saraswat, J De Kleer and B. Williams. \newblock In {\em proceedings of ILPS workshop on defeasible reasoning and constraint solving}, San Diego, USA, 1991. \bibitem{atms-focus} Forbus K. D. and de Kleer J. ``Focusing the ATMS'', {\it proceedings of the 7th National Conference on Artificial Intelligence}, St Paul, 1988. \bibitem{focus} P.~Codognet and P.~Sav\'eant, \newblock{A {M}etalanguage for {R}epresentation and {C}ontrol in {A}ssumption-based {P}roblem {S}olvers} , \newblock In {\em 2nd International Conference on Software and Knowledge Engineering}, Skokie, USA, 1990. \bibitem{pvh89} P.~Van~Hentenryck. \newblock {\em {Constraint Satisfaction in Logic Programming}}. \newblock Logic Programming Series, The MIT Press, Cambridge, MA, 1989. \bibitem{warren-andorra} D.H.D.~Warren. \newblock {The Andorra Principle}. \newblock Presented at the 1987 GigaLips workshop, University of Bristol. \bibitem{CostaWY91b} vV{\'{\i}}tor~Santos Costa, David H.~D. Warren, and Rong Yang. \newblock The {Andorra-I} engine: A parallel implementation of the basic andorra model. \newblock {\em Proceedings of the Eighth International Conference on Logic Programming}, pages 825--839, MIT Press, 1991. \bibitem{JansonHSLP91} Sverker Janson and Seif Haridi. \newblock Programming paradigms of the {A}ndorra kernel language. \newblock {\em Proceedings of the 1991 International Logic Programming Symposium}, pages 167--186, MIT Press, 1991. \bibitem{cc-fd} P. Van Hentenryck, V. Saraswat and Y. Deville. \newblock Constraint processing in cc(FD). \newblock submitted for publication, 1991. \bibitem{Str89} P. Struss and O. Dressler. \newblock Physical negation - integrating fault models into the General Diagnostic Engine. \newblock {\em proceedings of IJCAI 89}, Detroit, 1989. \end{thebibliography} } \newpage\appendix \input{ab_cc.pl} \end{document}