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

