\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) \begin{abstract} TBD \end{abstract} \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 diagnostic 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 diagnostic 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 diagnostic reasoning, and a short comparison with previous work on abduction is conducted in Section~7, followed by a short conclusion. \section{\cc{} languages} The central concept underlying \cc{} languages is that of a constraint system. Briefly, a constraint system is any system of partial information which comes equipped with notions of consistency and entailment. For the purposes of the present paper, we shall assume that such a constraint system $L$ is specified by a certain set of first-order formulas, and the entailment relation $\vdash $between finite sets of formulas and single formulas is obtained by interpreting these formulas in a certain pre-specified class of models. (Thus $c_1, \ldots, c_n \vdash c$ if in each model in this class, for all valuations for the free variables, $c$ must be true, whenever each of the $c_i$ are true.) More details and more general definitions may be found in \cite{Sar89} and \cite{SarLICS92}. In the following, for any finite set of variables $V$, we shall use the notation $L(V)$ to indicate the set of constraints whose free variables lie in $V$. 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{\mbox{Tell}}\axiom{\tuple{(\Gamma, c), s} \derives \tuple{\Gamma, s\cup\{c\}}}\\ \quad\\ \rname{\mbox{Ask}}\from{s \vdash d}% \infer{\tuple{(\Gamma, d \then A), s} \derives \tuple{(\Gamma,A),s}}\\ \quad\\ \axname{\mbox{Parallel Composition}}\axiom{\tuple{(\Gamma, (A_1,A_2)), s} \derives \tuple{(\Gamma,A_1,A_2), s}} \end{array} \end{equation} The operational semantics of the \cc{} languages has two abstract characterizations. The first is a logical characterization: in fact \cc{} programs can be directly read as first-order formulas and it can be shown that the operational semantics of \cc{} languages is sound and complete for first-order constraint entailment. This means the following. Say that $A \models_P c$ iff in all first-order models of the given program (built on top of the given models of the constraint system), every valuation satisfying $A$ satisfies $c$. Then we have that if $\tuple{A,\emptyset} \starderives \tuple{\Gamma, c}$, then $A \models_P c$ and if $A \models_P c$ then there is a $\Gamma$ and a $c'$ such that $\tuple{A, \emptyset}\starderives\tuple{\Gamma, c'}$ and $c' \vdash c$ \cite{cc-logic}. The second characterization is more direct. Agents are given denotations as closure operators over the underlying constraint system. The operator corresponding to an agent is merely the operator that maps each input to the limit of all fair execution sequences of the agent on that input. It is not hard to show that, because of the monotonic nature of ask and tell operations, the operators thus generated are monotone, idempotent and extensive, that is, are closure operators. Closure operators capture the essence of the notion of entailment: any set of inference rules can be associated with a closure operator which maps a set of formulas to their closure under the inference rules. Indeed closure operators were initially introduced by Tarski for precisely the purpose of characterizing the notion of logical entailment. It is rather remarkable that such a simple notion has turned out to provide a very simple natural and powerful mathematical interface between computation and logic (see, e.g., \cite{SRP91}). In particular, these operators enjoy a number of remarkable computational properties. The most important of these is that such operators can be completely characterized by the set of their fixed points --- for, each input is mapped by such an operator to its least fixed point above that input. Indeed, a number of computationally important operations on closure operator have rather simple definitions in terms of sets of fixed points. For example, the parallel composition of two closure operators $f$ and $g$ corresponds logically to their conjunction, and yields a closure operator whose fixed points are precisely the intersection of the fixed points of $f$ and $g$. \section{Abduction in \cc{} languages} We begin by giving an abstract description of the notion of abduction in a setting in which computation and deduction are captured by the notion of closure operators over first-order constraint systems. \begin{definition} Let $SD:L \rightarrow L$ be a closure operator, and $r \in L$ a constraint, and $V$ a set of variables. A constraint $e \in L(V)$ is an {\em explanation} for $r$ if $SD(e)$ is consistent and $SD(e) \geq r$. We shall write $e \explains_{SD,V} r$, and just $e \explains r$, when $SD$ and $V$ are clear from the context. An explanation is {\em minimal}, if, in addition, for any other explanation $e'$, it is the case that $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$). Alternatively, the given inference rules $f$ can be considered as transducers that transform a given output condition $r$ to one of perhaps many input conditions $i$, in the variables $V$, such that if $f$ is invoked in a store stronger than $i$, then the system is guaranteed to quiesce in a store stronger than $r$. A {\em minimal} explanation, is one which makes just as many assumptions as needed to obtain an explanation. The connections with Dijkstra's (weakest) pre-conditions for imperative programs are obvious. Clearly, there may be more than one explanation for a given $SD$, $r$ and $V$. We have: \begin{proposition} Assume $SD$ and $V$ 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 \vdash e$ implies $d \explains e$ \item $e \explains c$ whenever $e \vdash d$, $SD(e) < \false$, and $d \explains c$. \end{itemize} \end{proposition} %% Definition of normal form. \section{An operational abduction procedure} %% Abduction on deadlock, proof that we thus compute (minimal) explanations. 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 tuples of the form \tuple{\Gamma, s, d, V} where $d$ is a set of (abduced) constraints, $V$ the set of abducible variables, $s$ is a set of constraints, and $\Gamma$ is a multiset of agents. \begin{equation} \begin{array}{rll} \axname{\mbox{Tell}} \axiom{\tuple{(\Gamma, c), s, d, V} \derives \tuple{\Gamma, s\cup\{c\},d,V}}\\ \quad\\ \rname{\mbox{Ask}} \from{s \cup d \vdash c} \infer{\tuple{(\Gamma, c \then A), s, d, V} \derives \tuple{(\Gamma,A),s, d, V}}\\ \quad\\ \axname{\mbox{Parallel Composition}} \axiom{\tuple{(\Gamma, (A_1,A_2)), s, d, V} \derives \tuple{(\Gamma,A_1,A_2), s, d, V}}\\ \quad\\ \rname{\mbox{Abduction}} \from{\begin{array}{lll} \tuple{(\Gamma, c\then A), s, d, V)} \not\derives & s \cup d \cup c\not\vdash \false & \var(c)\subseteq V \end{array}} \infer{\tuple{(\Gamma, c \then A), s, d, V} \derives \tuple{(\Gamma,A),s, d \cup c, V}}\\ \end{array} \end{equation} \end{minipage}\\ \hline\end{tabular} \caption{Transition system for Abductive \cc{} language}\label{ab-trans-sem} \end{table} The transition system for Abductive \cc{} specifies how to compute explanations for agents. Below we discuss the connection between the abstract notion of explanation for closure operators, and the computational description provided by the operational semantics. \begin{definition} An abduction system $\alpha$ is a triple \tuple{A, V, P}, where $A$ is a \cc{} agent, $V$ a set of abducible variables, and $P$ a \cc{} program. \end{definition} For $\alpha$ such a system, we shall write $\explains_{\alpha}$ for the relation $\explains_{f_{\alpha}, V}$, where $f_{\alpha}$ is the closure operator generated by $A$ and $P$. \begin{definition} An abduction system $\alpha=\tuple{A, V, P}$ is said to {\em generate} an explanation $d$ for $e$ if there exists a $\Gamma$ and $c$, such that: $$\tuple{A, \emptyset, \emptyset, V} \starderives \tuple{\Gamma, c, d,V}\not\derives$$ and $d \cup c$ is consistent, and $d \cup c \vdash e$. \end{definition} \begin{theorem}[Soundness of Abductive \cc{}] If an abduction system $\alpha=\tuple{A, V, P}$ generates the explanation $d$ for $e$, then $d \explains_{\alpha} e$. \end{theorem} \begin{theorem}[Completeness of Abductive \cc{}] Let $\alpha=\tuple{A, V, P}$ be an abduction system, and assume that $d \explains_{\alpha} e$. Then there exists a $d'$ such that $\alpha$ generates the explanation $d'$ for $e$, and $d \vdash d'$. \end{theorem} In particular, note that for any abduction system $\alpha$, every minimal explanation $d$ for $e$ is generable. \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 asks 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 diagnostic reasoning} Our main application topic is diagnostic 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 diagnostic reasoning for two main reasons. First, because diagnostic 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 diagnostic reasoner. In the examples that follow, we assume implemented a top-level interface {\tt abduce(Agent, Vars, Conclusion)} which takes a \cc{} agent, a list of variables (and their names), and a set of constraints, and prints out the constraints in the specified variables that need to be assumed so that running {\tt Agent} will produce {\tt Conclusions}. \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 \then (Left=0, Right=0), Mode=ok \then (Left=plus, Right=plus).. \agent wire(State,In,Out) :: State=ok \then In=Out, State=broken \then Out=0.. \agent bulb(State,Light,Left,Right) :: State=ok \then \R(Left=plus, Right=plus \then Light=on), (Left=0 \then Light=off), (Right=0 \then Light=off)\L, State=damaged \then 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 \then table(Type, In1, In2, Out)), (Id=stuck\_at\_0 \then Out = 0), (Id=stuck\_at\_1 \then 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) :: 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 truly relates abduction and constraint solving. Thanks to the generality of \cc{} languages, it emcompasses 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{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{SarLICS92} V.A. Saraswat. \newblock {The category of constraint systems is Cartesian-closed}. \newblock In {\em {Proceedings of the IEEE Symposium on Logic in Computer Science}}, Santa Cruz, Ca, June 1992. \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} V{\'{\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_new.pl} \end{document}