\documentstyle[jair,twoside,11pt,theapa]{article}
%\input epsf %% at top of file
 
\jairheading{1}{1993}{91-107}{8/93}{11/93}
\ShortHeadings{The Difficulties of Learning Logic Programs with Cut}%
{Bergadano, Gunetti, \& Trinchero}
\firstpageno{91}
 
\title{The Difficulties of Learning Logic Programs with Cut}
 
\author{\name Francesco Bergadano \email bergadan@di.unito.it \\
       \addr Universit\`{a} di Catania, Dipartimento di Matematica, \\
       via Andrea Doria 6, 95100 Catania, Italy
       \AND
       \name Daniele Gunetti \email gunetti@di.unito.it \\
       \name Umberto Trinchero \email trincher@di.unito.it \\
       \addr Universit\`{a} di Torino, Dipartimento di Informatica, \\
       corso Svizzera 185, 10149 Torino, Italy}
\newtheorem{newdef}{Definition}
 
\begin{document}
 
\maketitle
 
\begin{abstract}
As real logic programmers normally use cut (!), an effective learning
procedure for logic programs should be able to deal with it.
Because the cut predicate has only a procedural meaning,
clauses containing cut cannot be learned using an extensional
evaluation method, as is done in most learning systems.
On the other hand, searching a space of possible programs
(instead of a space of independent clauses) is unfeasible.
An alternative solution is to generate first a candidate
base program which covers the positive examples, and then
make it consistent by inserting cut where appropriate.
The problem of learning programs with cut has not been
investigated before and this seems to be a natural and reasonable 
approach. We generalize this scheme and investigate 
the difficulties that arise.  Some of the major shortcomings 
are actually caused, in general, by the
need for intensional evaluation. As a conclusion, the analysis of this paper
suggests, on precise and technical grounds, that learning cut is difficult,
and current induction techniques should probably be restricted to purely
declarative logic languages.\\
 
\end{abstract}
 
%\renewcommand{\baselinestretch}{1.2} 
\small
\normalsize
 
\section{Introduction}
 
Much recent research in AI and Machine Learning
is addressing the problem of learning
relations from examples, especially under the
title of Inductive Logic Programming
\cite{muggilpw91}.
One goal of this line of research,
although certainly not the only one, is the
inductive synthesis of logic programs. More generally,
we are interested in the
construction of program development tools
based on Machine Learning techniques.
Such techniques now include efficient algorithms for
the induction of logical descriptions of recursive relations.
However, real logic programs contain features that are not
purely logical, most notably the cut (!) predicate.
The problem of learning programs with cut has
not been studied before in Inductive Logic Programming,
and this paper analyzes the difficulties involved.
 
\subsection{Why Learn Programs with Cut?}
 
There are two main motivations for learning logic programs
with cut:
 
\begin{enumerate}
\begin{item}
ILP should provide practical tools for developing logic programs,
in the context of some general program development methodology
(e.g., \cite{bergsigs93});
as real size
logic programs normally contain cut, learning cut will
be important for creating an integrated Software
Engineering framework.
\end{item}
\begin{item}
Extensive use of cut can make programs sensibly shorter, and
the difficulty of learning a given logic program is
very much related to its length.
\end{item}
\end{enumerate}
 
For both of these objectives, we need not only cuts that
make the programs more efficient without changing their input-output
behavior (``green cuts''), but also cuts
that eliminate some possible computed results (``red cuts'').
Red cuts are sometimes considered
bad programming style, but are often useful.
Moreover, only the red cuts
are effective in making programs shorter.
Green cuts are also important, and less controversial.
Once a correct program has been inferred via inductive methods,
it could be made more efficient through the insertion of
green cuts, either manually or by means of automated
program transformation techniques \cite{lopstrwo93}.
 
\subsection{Why Standard Approaches Cannot be Used?}
 
Most Machine Learning algorithms generate rules or
clauses one at a time and independently of each other:
if a rule is useful (it covers some positive example)
and correct (it does not cover any negative example), then
it is added to the description or program which is being
generated, until all positive examples have been covered.
This means that we are
searching a space of possible clauses, without backtracking.
This is obviously a great advantage, as programs are
sets of clauses, and therefore the space of possible programs
is exponentially larger.
 
The one principle which allows this simplification of the problem
is the $extensional$ evaluation of possible clauses, used to
determine whether a clause C $covers$ an example $e$.
The fact that a clause C covers an example $e$ is then
used as an approximation of the fact that a logic program containing
C derives $e$.
Consider, for instance, the clause C = ``p(X,Y) $\leftarrow$ $\alpha$'', 
and suppose the example $e$ is p(a,b).
In order to see whether C covers $e$, the extensionality
principle makes us evaluate any literal in $\alpha$ as
true if and only if it matches some given positive example.
For instance, if
$\alpha$ = q(X,Z) $\wedge$ p(Z,Y),
then the example p(a,b) is $extensionally$
$covered$ iff there is a ground term c such that
q(a,c) and p(c,b) are given as positive examples.
In particular, in order to obtain the truth value of
p(c,b), we will not need to call other clauses
that were learned previously.
For this reason, determining whether C covers $e$ only
depends on C and on the positive examples. Therefore, the
learning system will decide whether to accept C as
part of the final program P independently of the
other clauses P will contain.
 
The extensionality principle is found in Foil \cite{quinmljo90}
and its derivatives, but is also used in bottom-up
methods such as Golem \cite{muggaltc90}. Shapiro's MIS system
\cite{shapbook83} uses it when refining clauses, although
it does not when backtracing inconsistencies.
We have also used an extensional evaluation of clauses 
in the FILP system \cite{bergijca93}.
 
When learning programs with cut, clauses are no longer
independent and their stand-alone extensional evaluation
is meaningless. 
When a cut predicate is evaluated, other possible
clauses for proving the same goal will be ignored.
This changes the meaning of these other clauses.
Even if a clause extensionally covers some example $e$, it
may be the case that the final program does not derive $e$,
because some derivation paths have been eliminated
by the evaluation of a cut predicate.
 
However, an exhaustive search in a space of programs is 
prohibitive. Learning methods, even if based on 
extensionality, are often considered inefficient if
sufficient prior information is not available; searching
for $sets$ of clauses will be exponentially worse.
This would amount to a brute-force enumeration of
all possible logic programs containing cut, until
a program that is consistent with the given examples is found.
 
\subsection{Is there an Alternative Method?}
 
Cut will only eliminate some computed results, i.e., after
adding cut to some program, it may be the case that some 
example is no longer derived. This observation suggests a
general learning strategy: a base program P is induced
with standard techniques, given the positive and maybe
some of the negative examples, then the remaining negative
examples are ruled out by inserting cut in some clause of P.
Obviously, after inserting cut, we must make sure that the
positive examples may still be derived.
 
Given the present technology and the discussion above, this
seems to be the only viable path to a possible solution.
Using standard techniques, the base program P would be generated
one clause at a time, so that the positive examples are
extensionally covered. However, we think this view is too restrictive,
as there are programs which derive all given positive
examples, although they do not cover them extensionally
\cite{bergtkde93,deraijca93}. 
More generally, we consider
traces of the positive examples:
 
\begin{newdef}
Given a hypothesis space S of possible clauses, and
an example e such that S $\vdash$ e, the set of
clauses T$\subseteq$S which is used during the derivation of e
is called a {\em trace} for e.
\end{newdef}
 
We will use as a candidate base program P any subset of
S which is the union of some traces for the positive examples.
If P$\subseteq$S extensionally covers the positive examples,
then it will also be the union of such traces, but the
converse is not always true. After a candidate program has
been generated, an attempt is made to insert cuts so that
the negative examples are not derived. If this is successful,
we have a solution, otherwise, we backtrack to another
candidate base program. We will analyze the many problems inherent in
learning cut with this class of trace-based learning methods,
but, as we discuss later (Section 4),
the same problems need to be faced
in the more restrictive framework of extensional evaluation.
In other words, even if we choose to learn the base program 
P extensionally, and then we try to make it consistent by
using cut, the same computational problems would still arise.
The main difference is that standard
approaches based on extensionality do not allow for backtracking
and do not guarantee that a correct solution is found \cite{bergtkde93}.
 
As far as computational complexity is concerned, trace-based
methods have a complexity standing 
between the search in a space of independent
clauses (for the extensional methods) and the exhaustive search
in a space of possible programs. We need the following:
 
\begin{newdef}
Given a hypothesis space S, the {\em depth} of an example e
is the maximum number of clauses in S successfully used in the derivation
of e.
\end{newdef}
 
For example, if we are in a list processing domain, and
S only contains
recursive calls
of the type
``P([H$|$T]) :- ..., P(T), ...''
then the depth of an example P(L) is the length of L.
For practical program induction tasks, it
is often the case that the depth of an example is
related to its complexity, and not to the hypothesis space S.
If $d$ is the maximum depth for the given $m$ positive examples,
then the complexity of trace-based methods is of the order
of $|S|^{md}$, while extensional methods will just enumerate
possible clauses with a complexity which is linear in $|S|$, and
enumerating all possible programs is exponential in $|S|$.
 
\section{ A Simple Induction Procedure }
 
The trace-based induction procedure we analyze here
takes as input a finite set of clauses S 
and a set of positive and negative
examples E+ and E- and tries to find a subset T of S such that T derives
all the positive examples and none of the negative examples. 
For every positive example e+ $\in$ E+,  we assume that S is large enough
to derive it. Moreover, we assume that all clauses in S are
flattened\footnote{A clause is $flattened$ if it does not contain
any functional symbol. Given an unflattened clause, it is alway possible
to flatten it (by turning functions into new predicates with an additional
argument representing the result of the function) 
and vice versa \cite{rouvmljo94}.}. 
If this is not the case, clauses are flattened
as a preprocessing step. 
 
We consider one possible proof for S $\vdash$ e+, and we
build an intermediate program T $\subseteq$ S containing a trace of
the derivation. The same is done
for the other positive examples, and the corresponding traces T are
merged.
Every time T is updated, it is checked against the negative
examples. If some of them are derived from T, 
cut (!) is inserted in the antecedents of the clauses in T,
so that a consistent program
is found, if it exists.
If this is not the case, the procedure backtracks to 
a different proof for S $\vdash$ e+.
The algorithm can be informally described as follows:\\
 
%\newpage
 
%\renewcommand{\baselinestretch}{1.0}
\small
\normalsize
 
\noindent
input: a set of clauses S\\
\hspace*{0.5in} a set of positive examples E+\\
\hspace*{0.5in} a set of negative examples E-\\
S := flatten(S)\\
T $\leftarrow$ $\emptyset$ \\
For each positive example e+ $\in$ E+\\ 
\hspace*{0.5in} find T1 $\subseteq$ S such that 
T1 $\vdash_{SLD}$ e+ (backtracking point 1)\\
\hspace*{0.5in} T $\leftarrow$ T $\cup$ T1\\
\hspace*{0.5in} if {\sf T derives some negative example e-} then  {\sf trycut}(T,e-)\\
\hspace*{0.5in} if {\sf trycut}(T,e-) fails then backtrack\\
output the clauses listed in T \\
 
\noindent
{\sf trycut}(T,e-):\\
insert ! somewhere in T (backtracking point 2) so that\\
\hspace*{0.5in} 1. all previously covered positive examples are 
still derived from T, and\\
\hspace*{0.5in} 2. T $\not\vdash_{SLD}$ e-\\
 
%\renewcommand{\baselinestretch}{1.2} 
\small
\normalsize
 
\noindent
The complexity of adding cut somewhere in the trace T, 
so that the negative example e- is no longer derived, 
obviously only depends on the size of T.
But this size depends on
the depth of the positive examples, not on the size of the
hypothesis space S. Although more clever ways of doing this
can be devised, based on the particular example e-, we
propose a simple enumerative technique in the implementation
described in the Appendix.
 
\section{Example: Simplifying a List}
 
In this section we show an example of the use of the induction procedure
to learn the logic program ``$simplify$''.
$Simplify$ takes as input a list  
whose members may be lists, and transforms it into a ``flattened'' list of
single members, containing no repetitions and no lists as members.
This program  appears as exercise number 25 in \cite{prolbyex88}, is composed
of nine clauses (plus the clauses
for $append$ and $member$);  six of them are recursive, 
one is doubly-recursive
and cut is extensively used. Even if $simplify$ is a not a very complex
logic program, it is more complex than usual ILP test cases.
For instance, the $quicksort$ and $partition$ program, which is very often
used, is composed
of only five clauses (plus those for $append$), 
and three of them are recursive.
Moreover, note that the conciseness of $simplify$ is essentially 
due to the extensive use of cut. Without cut, this program would be
much longer. In general, the longer a logic program,
the more difficult to learn it.
 
As a consequence, we start with a relatively strong bias;
suppose that the following 
hypothesis space of N=8449 possible clauses is defined
by the user:
 
\begin{itemize}
\begin{item}
The clause ``simplify(L,NL) :- flatten(L,L1), remove(L1,NL).''
\end{item}
\begin{item}
All clauses whose head is ``flatten(X,L)'' and whose body is composed
of a conjunction of any of the following literals:\\
 
\noindent
head(X,H), tail(X,L1), equal(X,[L1,T]),
null(T),
null(H),
null(L1),
equal(X,[L1]),\\
flatten(H,X1), flatten(L1,X2),\\
append(X1,X2,L), assign(X1,L),
assign(X2,L),
list(X,L).\\
\end{item}
\begin{item}
All clauses whose head is ``remove(IL,OL)'' and whose body is composed
of a conjunction of any of the following literals:\\
 
\noindent
cons(X,N,OL),
null(IL), assign([],OL),\\
head(IL,X), tail(IL,L), member(X,L),
remove(L,OL), remove(L,N).\\
\end{item}
\begin{item}
The correct clauses for $null$,
$head$, $tail$,
$equal$, $assign$, 
$member$, $append$ 
are given:\\
 
\noindent
null([]).\\
head([H$|$\_],H).\\
tail([\_$|$T],T).\\
equal(X,X).\\
assign(X,X).\\
member(X,[X$|$\_]).\\
member(X,[\_$|$T]) :- member(X,T).\\
append([],Z,Z).\\
append([H$|$X],Y,[H$|$Z]) :- append(X,Y,Z).
\end{item}
\end{itemize}
 
\noindent
By using various kinds of constraints, the initial number of clauses
can be strongly reduced. Possible constraints are the following:
 
\begin{itemize}
\begin{item}
Once an output is produced it must not be instantiated again. This means
that any variable cannot occur as output in the antecedent more than once.
\end{item}
\begin{item}
Inputs must be used: all input variables in the head of a clause must 
also occur in its antecedent.
\end{item}
\begin{item}
Some conjunctions of literals are ruled out because they can 
never be true, e.g.  null(IL)$\wedge$head(IL,X).
\end{item}
\end{itemize}
By applying various combination of these constraints it is possible
to strongly restrict
the initial hypothesis space, which is then 
given in input to
the learning procedure.
The set of positive and negative examples used in the learning task
is:\\
 
\noindent
simplify\_pos([[[],[b,a,a]],[]],[b,a]). remove\_pos([a,a],[a]).\\
(simplify\_neg([[[],[b,a,a]],[]],X),not equal(X,[b,a])).\\
simplify\_neg([[a,b,a],[]],[a,[b,a]]). remove\_neg([a,a],[a,a]).\\
 
\noindent
Note that we define some negative examples of $simplify$ to be all the
examples with the same input of a given positive example and 
a different output, for instance
simplify\_neg([[[],[b,a,a]],[]],[a,b]).
Obviously, it is also possible to give
negative examples as normal ground literals. 
The learning procedure outputs the program for
$simplify$ reported below, which turns out to be substantially
equivalent to the one described in \cite{prolbyex88} (we have 
kept clauses unflattened).\\
 
%\renewcommand{\baselinestretch}{1.0}
\small
\normalsize
 
\noindent
simplify(L,NL) :- flatten(L,L1), remove(L1,NL).\\
 
\noindent
flatten(X,L) :- equal(X,[L1,T]), null(T), !,
flatten(L1,X2), assign(X2,L).\\
%\hspace*{1.1in}flatten(L1,X2), assign(X2,L).\\
flatten(X,L) :- head(X,H), tail(X,L1), null(H), !,
flatten(L1,X2), assign(X2,L).\\
%\hspace*{1.1in}flatten(L1,X2), assign(X2,L).\\
flatten(X,L) :- equal(X,[L1]), !, flatten(L1,X2), assign(X2,L).\\
flatten(X,L) :- head(X,H), tail(X,L1), !,\\
\hspace*{1.1in}flatten(H,X1), !, flatten(L1,X2), append(X1,X2,L).\\
flatten(X,L) :- list(X,L).\\
 
\noindent
remove(IL,OL) :- head(IL,X), tail(IL,L), member(X,L), !, remove(L,OL).\\
remove(IL,OL) :- head(IL,X), tail(IL,L), remove(L,N), cons(X,N,OL).\\
remove(IL,OL) :- null(IL), assign([],OL).\\
 
%\renewcommand{\baselinestretch}{1.2}
\small
\normalsize
 
\noindent
The learning task takes about 44 seconds on our implementation. However,
This is obtained at some special conditions, which are thoroughly
discussed in the next sections:
 
\begin{itemize}
\begin{item}
All the constraints listed above are applied, so that the 
final hypothesis space is reduced to less than one hundred clauses.
\end{item}
\begin{item}
Clauses in the hypothesis space are generated in the correct
order, as they must appear in the final program. Moreover, literals
in each clause are in the correct position. This is important,
since in a logic program with cut the relative position of clauses
and literals is significant. As a consequence, we can learn $simplify$
without having to 
test for different clause and literal orderings (see subsections 4.2 and 4.5).
\end{item}
\begin{item}
We tell the learning procedure to use at most two cuts per clause.
This seems to be quite an intuitive constraint since,
in fact, many classical logic programs have no more than one cut
per clause (see subsections 4.1 and 5.4). 
\end{item}
\end{itemize}
 
\section{Problems}
Experiments with the above induction procedure have shown 
that many problems arise when learning logic programs 
containing cut. In the following, we analyze these problems, and this 
is a major contribution of the present paper. As cut cannot
be evaluated extensionally, this analysis is
general, and does not depend
on the specific induction method adopted. Some possible 
partial solutions will be discussed in Section 5.
 
\subsection{Problem 1: Intensional Evaluation, Backtracking and Cut}
The learning procedure of Section 2 is very simple, but it can be 
inefficient. However, we believe this is common to every intensional
method, because clauses cannot be 
learned independently of one another.
As a consequence,
backtracking cannot be avoided and this can have some impact
on the complexity of the learning process.
Moreover, cut must be added to every trace covering negative examples.
If no constraints are in force, we can range from only one cut in the
whole trace to a cut between each two literals of each clause in the trace.
Clearly, the number of possibilities is exponential in the number of
literals in the trace. Fortunately, this number is usually much smaller than
the size of the hypothesis space, as it depends on the depth of the 
positive examples.
 
However, backtracking also has some advantages; in particular,
it can be useful
to search for alternative solutions.
These alternative programs can then be confronted
on the basis of any required characteristic, such as simplicity
or efficiency.
For example, using backtracking we discovered a version of $simplify$
equivalent to the one given but without the cut predicate between the
two recursive calls of the fourth clause of $flatten$.
 
\subsection{Problem 2: Ordering of Clauses in the Trace} 
In a logic program containing cut, the mutual position of clauses
is significant, and a different ordering can lead to
a different (perhaps wrong) behavior of the program.
For example, the following program for $intersection$:\\
 
\noindent
$c_1$) int(X,S2,Y) :- null(X), null(Y).\\
$c_2$) int(X,S2,Y) :- head(X,H), tail(X,Tail), 
member(H,S2), !, int(Tail,S2,S), cons(H,S,Y).\\
$c_3$) int(X,S2,Y) :- head(X,H), tail(X,Tail), int(Tail,S2,Y).\\
 
\noindent
behaves correctly only if $c_2$ comes before $c_3$. Suppose the
hypothesis space given in input to the induction procedure 
consists of the same three clauses as above, but with $c_3$
before $c_2$. If $\neg$$int$([a],[a],[]) is given as a negative
example, then the learning task fails, because clauses $c_1$ and
$c_3$ derive that example.
 
In other words, learning a program containing cut means not only
to learn a set of clauses, but also a specific ordering for 
those clauses. In terms of our induction procedure this means that 
for every trace T covering some negative example, we must check
not only every position for inserting cuts,
but also every possible clause ordering in the trace. 
This ``generate and test'' behavior is not difficult to implement,
but it can dramatically decrease the performance of the learning task.
In the worst case all possible permutations must be generated and 
checked, and this requires a time proportional to ($md$)!
for a trace of $md$ clauses\footnote{it must be noted that if we are learning 
programs for two different predicates, of $j$ and $k$ clauses
respectively (that is, $md$ = $j$+$k$), 
then we have to consider not ($j$+$k$)! different
programs, but only $j$!+$k$!. We can do better if, inside a program,
it is known that non-recursive clauses have a fixed position, 
and can be put before or after of all the recursive clauses.}.
 
The necessity to test for different permutations of
clauses in a trace is a 
primary source of inefficiency when learning programs with cut,
and probably the most difficult problem to solve.
 
\subsection{Problem 3: Kinds of Given Examples}

Our induction procedure
is only able to learn programs which are traces, i.e. where
every clause in the program is used to derive at least one positive
example. When learning definite clauses, this is not a problem, because
derivation is monotone, and for every program P, complete and consistent
w.r.t. the given examples, there is a program P$^\prime$$\subseteq$P which is
also complete and consistent and is a trace\footnote{
a learned program P is $complete$ if it derives all
the given positive examples, and it is $consistent$ if it does not
derive any of the given negative examples}.
On the other hand, when learning clauses containing cut, 
it may happen that the only complete and consistent 
program(s) in the hypothesis space 
is neither a trace, nor
contains it as a subset. This is because derivation is no longer
monotone and it can be the case that a negative example is derived by
a set of clauses, but not by a superset of them, as in the following
simple example:\\
 
\noindent
S = \{sum(A,B,C) :- A$>$0, !, M is A-1, sum(M,B,N), C is N+1.\\
\hspace*{0.4in}sum(A,B,C) :- C is B.\}\\
sum\_pos(0,2,2), sum\_neg(2,2,2).\\
 
\noindent
The two clauses in the hypothesis space
represent a complete and consistent program for
the given examples, but our procedure
is unable to learn it. Observe that the
negative example is derived by the second clause,
which is a trace for the positive example, but not by
the first and the second together. 
 
This problem can be avoided if we require
that, for every negative example,
a corresponding positive example with the same input be given
(in the above case, the example required is sum\_pos(2,2,4)).
In this way, if a complete program exists in the hypothesis space, 
then it is also a trace, and can be learned. Then it
can be made consistent using cut,  in order to rule out the derivation
of negative examples. 
The constraint on positive and negative examples seems to be quite 
intuitive. In fact,  when writing a program,
a programmer usually thinks in terms of what a program
should compute on given inputs, 
and then tries to avoid wrong computations for those inputs. 
 
\subsection{Problem 4: Ordering of Given Examples} 
When learning clauses with cut, even 
the order of the positive examples may be significant. In the
example above, if sum\_pos(2,2,4) comes after sum\_pos(0,2,2) then
the learning task
fails to learn a correct program for $sum$, because it cannot find a
program consistent w.r.t. the first positive example and the negative one(s).
 
In general, for a given set of $m$ positive examples
this problem can be remedied by testing different example orderings.
Again, in the worst case $k$! different orderings of a set 
of $k$ positive examples must be checked. Moreover, 
in some situations a favorable ordering does not exist. Consider
the following hypothesis space:\\
 
\noindent
$c_1$) int(X,Y,W) :- head(X,A), tail(X,B), notmember(A,Y), int(B,Y,W).\\
$c_2$) int(X,Y,W) :- head(X,A), tail(X,B), notmember(A,Y), !, int(B,Y,W).\\
$c_3$) int(X,Y,Z) :- head(X,A), tail(X,B), int(B,Y,W), cons(A,W,Z).\\
$c_4$) int(X,Y,Z) :- head(X,A), tail(X,B), !, int(B,Y,W), cons(A,W,Z).\\
$c_5$) int(X,Y,Z) :- null(Z).\\
 
\noindent
together with the set of examples:\\
 
\noindent
$e_1$) int\_pos([a],[b],[ ]).\\
$e_2$) int\_pos([a],[a],[a]).\\
$e_3$) int\_neg([a],[b],[a]).\\
$e_4$) int\_neg([a],[a],[ ]).\\
 
 
\noindent
Our induction procedure will not be able to find a correct program 
for any ordering of the two positive examples,
even if such a program does exist
([$c_2$,$c_4$,$c_5$]). This  program is the union
of two traces: [$c_2$,$c_5$], which covers $e_1$, and [$c_4$,$c_5$],
which covers $e_2$. Both of these traces are inconsistent,
because the first covers $e_4$,
and the second covers $e_3$.
This problem can be remedied 
only if all the positive examples are derived before the check
against negative examples is done. 
 
However, in that case 
we have a further loss of efficiency,
because some inconsistent traces are discarded only in the end.
In other words, we would need to learn a 
program covering $all$ the positive examples, and then make it
consistent by using cut and by reordering clauses.
Moreover, there can be no way to make a program consistent
by using cut and reorderings. As a consequence, all the time used
to build that program is wasted. As an example, suppose we are
given the following hypothesis space:\\
 
\noindent
$c'_1$) int(X,Y,Z) :- head(X,A), tail(X,B), int(B,Y,W), cons(A,W,Z).\\
$c'_2$) int(X,Y,Z) :- null(X), null(Z).\\
$c'_3$) int(X,Y,Z) :- null(Z).\\
 
\noindent 
with the examples:\\
 
\noindent
$e'_1$) int\_pos([a],[a],[a]).\\
$e'_2$) int\_pos([a,b],[c],[]).\\
$e'_3$) int\_neg([a],[b],[a]).\\
 
\noindent
Then we can learn the trace [$c'_1$,$c'_2$] from $e'_1$ and the trace
[$c'_3$] from $e'_2$. But [$c'_1$,$c'_2$,$c'_3$] covers $e'_3$, and there
is no way to make it consistent using cut or by reordering its clauses. 
In fact, the first partial trace is responsible for this inconsistency, and 
hence the time used to learn [$c'_3$] is totally wasted.
 
Here it is also possible to understand why we need flattened clauses.
Consider the following program for $intersection$, which is 
equivalent to [$c_2$,$c_4$,$c_5$], but with the three clauses
unflattened:\\
 
\noindent
$u_2$) int([A$|$B],Y,W) :- notmember(A,Y), !, int(B,Y,W).\\
$u_4$) int([A$|$B],Y,[A$|$W]) :- !, int(B,Y,W).\\
$u_5$) int(\_,\_,[]).\\
 
\noindent
Now, this program covers int\_neg([a],[a],[]), 
i.e. [$u_2$,$u_4$,$u_5$] $\vdash$ int([a],[a],[]). In fact, clause $u_2$
fails on this example because a is a member of [a]. Clause $u_4$
fails because the empty list cannot be matched with [A$|$W]. But
clause $u_5$ succeeds because its arguments match those of the negative
example. As a consequence, this program would be rejected by the
induction procedure.
 
The problem is that, 
if we use unflattened clauses, it may happen that a clause body is
not evaluated because an example does not match the head
of the clause. As a consequence,
possible cuts in that clause are not evaluated and cannot influence the behavior
of the entire program. In our example, the cut in clause $u_4$ has no
effect because the output argument of int([a],[a],[]) does not match
[A$|$W], and the body of $u_4$ is not evaluated at all. Then $u_5$ is 
fired and the negative example is covered.  In the flattened version, 
clause $c_4$ fails only when cons(a,[],[])
is reached, but at that point a cut
is in force and clause $c_5$ cannot be activated.
Note that program [$u_2$,$u_4$,$u_5$] behaves correctly on the query
int([a],[a],X), and gives X=[a] as the only output.
 
\subsection{Problem 5: Ordering of Literals}
Even the relative position of literals
and cut in a clause is significant. 
Consider again the correct program
for $intersection$ as above ([$c_2$,$c_4$,$c_5$]), 
but with $c_4$ modified by putting the $cons$ literal in front of the
antecedent:\\
 
\noindent
$c'_4$) int(X,Y,Z) :- cons(A,W,Z), head(X,A), tail(X,B), int(B,Y,W).\\
 
\noindent
Then, there is no way to get a correct program for intersection
using this clause. To rule out the negative example
int\_neg([a],[a],[]) we must put a cut before the $cons$ predicate,
in order to prevent the activation of $c_5$. But, then, 
some positive examples are no longer covered, such as int\_pos([a],[],[]).
In fact, we have a wrong behavior every time 
clause $c'_4$ is called and fails,
since it prevents the activation on $c_5$.
In general, this problem cannot be avoided even by reordering clauses:
if we put $c'_4$ after $c_2$ and $c_5$, then int\_neg([a],[a],[])
will be covered.
As a consequence, we should also test for every possible permutation
of literals in every clause of a candidate program.
 
\section{Situations where Learning Cut is still Practical}
 
From the above analysis, learning cut appears to be difficult since,
in general, a learning procedure should be able to backtrack on the
candidate base programs (e.g., traces), on the position of cut(s) in
the program, on the order of the clauses in the program, on the
order of literals in the clauses and on the order
of given positive examples. However,
we have spotted some general conditions at which learning 
cut could still be 
practical. Clearly, these conditions cannot be a final solution to 
learning cut, but, if applicable, can alleviate the computational problems
of the task.
 
\subsection{Small Hypothesis Space}
First of all, a restricted hypothesis space is necessary. If clauses
cannot be learned independently of one another, a small hypothesis
space would help to limit the backtracking required on candidate
traces (problem 1). Moreover, even the number of clauses
in a trace would be probably 
smaller, and hence also the number of different
permutations and the number of
different positions for inserted cuts (problems 2 and 1).
A small trace would also have a slight positive impact on the need
to test for different literal orderings in clauses (problem 5).
 
In general, many kinds of constraints can be applied to keep a
hypothesis space small,
such as
ij-determinism \cite{muggaltc90}, 
rule sets and schemata \cite{wrobilpw91,bergijca93}, determinations
\cite{russaaai88}, locality \cite{coheijcw93}, etc (in fact,
some of these restrictions and others, such as those listed in 
Section 3,
are available in the actual implementation of our procedure -
see the Appendix\footnote{We found these constraints particularly useful.
By using them we were often able to restrict a hypothesis space of 
one order of magnitude without ruling out any possible solution.}). 
Moreover, candidate recursive clauses must be 
designed so that no
infinite chains of recursive calls can take place \cite{bergijca93}
(otherwise the learning task itself could be non-terminating).
In general, the number of possible recursive calls must
be kept small, in order to avoid too much backtracking
when searching for possible traces.
However, general constraints may not be sufficient. 
The hypothesis space must be designed carefully from the very 
beginning, and this can be difficult.
In the example of learning $simplify$ an initial hypothesis space 
of ``only'' 8449 clauses was obtained specifying not only the set
of required predicates, but even the variables occurring in every literal.
 
If clauses cannot be learned independently,
experiments have shown to us that a
dramatic improvement of the learning task can be obtained by
generating the clauses in the hypothesis space so that recursive clauses,
and in general more complex clauses, are taken into consideration
after the simpler and non-recursive ones. 
Since simpler and non recursive clauses require less time to be evaluated,
they will have a small impact on the learning time.
Moreover, learning simpler clauses (i.e. shorter) also alleviates problem 5.
 
Finally, it must be noted that our induction procedure does not
necessarily require that the hypothesis space S of possible clauses
be represented explicitly.
The learning task could start with an empty set S
and an implicit description of the hypothesis space, for example
the one given 
in Section 3. When a positive example cannot be derived from S,
a new clause is asked for to a clause generator and added to 
S. This step is repeated until the example is derivable from the updated S, and
then the learning task can proceed normally.
 
\subsection{Simple Examples}
 
Another improvement can be achieved by using examples that
are as simple as possible. In fact, each
example which may involve a recursive call is potentially responsible
for the activation of all the corresponding clauses 
in the hypothesis space.
The more complex the example, the larger the number
of consecutive recursive activations of clauses and the
larger the number of traces to be considered for backtracking (problem 1). 
For instance, to learn the $append$ relation, it may be sufficient
to use an example like append([a],[b],[a,b]) instead of one like
append([a,b,c,d],[b],[a,b,c,d,b]). Since simple examples would probably
require a smaller number of different clauses to be derived, this
would result in smaller traces, alleviating the problem of permutation
of clauses and literals in a trace (problems 2 and 5) 
and decreasing the number of positions for cuts (problem 1).
 
\subsection{Small Number of Examples}
Since a candidate program is formed by taking 
the union of partial traces learned for single examples, if we want
a small trace (problems 2 and 5) we must use
as few examples as possible, while still completely 
describing the required concept.
In other words, we should avoid redundant 
information. For example, if we want to learn the program for $append$,
it will be normally sufficient to use only one of the two positive
examples append([a],[b],[a,b]) and append([c],[d],[c,d]). Obviously it
may happen that different examples are 
derived by the same set of clauses,
and in this case the final program does not change. 
 
Having to check for all possible orderings
of a set of positive examples,
a small number of examples is also a solution to problem 4.
Fortunately, experiments have shown that normally very
few positive examples are needed to learn a program, 
and hence the corresponding number of different orderings is, 
in any case, a small number.
Moreover, since in our method a positive 
example is sufficient to learn all the clauses necessary to derive it, 
most of the time a complete program can be learned using only one
well chosen example. If such an example can be found (as in the case
of the learning task of section 3, where only one example of $simplify$
and one of $remove$ are given),
the computational problem of testing different
example orderings is automatically solved.
 
However, it must be noted that, in general, a small
number of examples may not be sufficient, except for very simple
programs. In fact, if we want to learn logic programs such as
$member$, $append$, $reverse$ and so on, then any example 
involving recursion will be sufficient. But for more complex
programs the choice may not be trivial. For example, our procedure
is able to learn the $quicksort$ (plus $partition$) program with
only one ``good'' example. But if one does not know how 
$quicksort$ and $partition$ work, it is likely that she or he will provide
an example allowing to learn only a partial description of $partition$.
This is particularly clear in the example of $simplify$. Had we used
the positive example 
simplify\_pos([[[],[b,a,a]]],[b,a]) (which is very close to the one 
effectively used), the first clause of $flatten$ would not have been
learned. In other words, to give few examples we must give good
examples, and often this is possible only by having in mind (at least
partially and in an informal way) 
the target program. Moreover, for complex programs,
good examples can mean complex examples, and this is in
contrast with the previous requirement.
For further studies of learning from good examples we refer the reader to 
the work of Ling (1991) and Aha, Ling, Matwin and Lapointe (1993).
 
\subsection{Constrained Positions for Cut and Literals}
 
Experiments have shown that it is not practical to allow the learning
procedure to test all possible positions of cut in a trace, even 
if we are able to keep the number of clauses in a trace small. 
The user must be able to indicate the positions
where a cut is allowed to occur, e.g., at the beginning of a 
clause body,
or before a recursive call. In this case,
many alternative programs with cut are 
automatically ruled out and thus do not have to be tested 
against the negative examples. It may also be useful to limit the 
maximum number of cuts per clause or per trace. For example, 
most of the time one cut per clause can be sufficient to learn a
correct program. In the actual implementation of our procedure,
it is in fact possible to specify the exact position of  cut 
w.r.t. a literal or a group of literals within each clause of
the hypothesis space, when this information is known.
 
To eliminate the need to test for different ordering of literals
(problem 5), we may also impose a particular global order,
which must be maintained in every clause of the hypothesis space.
However this requires a deep knowledge of the program we want,
otherwise some (or even all) solutions will be lost. Moreover, this 
solution can be in contrast with a use of constrained positions for cut,
since a solution program for a particular literal 
ordering and for particular positions for cuts may not exist.
 
\section{Conclusion}
 
Our induction procedure is based on
an intensional evaluation of clauses. 
Since the cut predicate has no declarative meaning,
we believe that intensional evaluation of
clauses cannot be abandoned, independently of the 
kind of learning method adopted. This can 
decrease the performance of the learning task, compared with
extensional methods, which examine clauses one at a time
without backtracking. However, the computational problems outlined in
Section 4 remain even if we choose to learn a complete program 
extensionally, and then we try to make it consistent by inserting cut.
The only difference is that we do not have backtracking (problem 1),
but the situation is probably worse, since extensional methods can fail
to learn a complete program even if it exists in the hypothesis space.
\cite{bergtkde93}.
 
Even if the ability to learn clauses containing procedural
predicates like cut seems to be fundamental to learning ``real'' 
logic programs, in particular  
short and efficient programs,
many  problems influencing the complexity 
of the learning task
must be faced. These include the number
and the relative ordering of clauses and literals in the hypothesis space, 
the kind and the relative ordering of given examples. 
Such problems seem to be related to the need for an
intensional evaluation of clauses in general, and not to the particular
learning method adopted. Even just to alleviate these problems, it seems
necessary to know a lot about the target program.
An alternative solution is simply to ignore some of the problems.
That is, avoid testing for different clause and/or literal and/or example
orderings.
Clearly, in this way the learning process can become feasible,
but it can fail to find a solution even when it exists.
However, many ILP systems 
(such as Foil) adopt such an ``incomplete-but-fast'' approach,
which is guided by heuristic information.
 
As a consequence, we view results presented in this paper 
as, at least partially, negative.
The problems we raised appear computationally difficult, and
suggest that attention should be restricted to purely
declarative logic languages, which are, in any
case, sufficiently expressive.
 
\acks{This work was in part supported by
BRA ESPRIT project 6020 on Inductive Logic Programming.}
 
 
\appendix
\section*{Appendix A}
 
The induction procedure of Section 2 is written in C-prolog 
(interpreted) and runs on a SUNsparcstation 1.
We are planning 
to translate it in QUINTUS prolog.
This Appendix contains a simplified description of its implementation.
As a preliminary step, in order
to record a trace of the clauses deriving a positive example e+, 
every clause in the 
hypothesis space\footnote{We assume clauses in the hypothesis space
to be flattened} S must be numbered and modified 
by adding to its body two literals.
The first one,
$allowed$($n$,$m$) is used to activate only the clauses which must be 
checked against
the negative examples.
The second one, $marker$($n$), is used to remember that clause number 
$n$ has been successfully used while deriving e+. 
Hence, in general, a clause in the hypothesis space S takes the following
form:\\
 
\noindent
$P$($X_1$,\ldots,$X_m$) :- $allowed$($n$,$m$),$\gamma$,$marker$($n$).\\
 
\noindent
where $\gamma$ is the actual body of the clause, $n$ is the
number of the clause in the set and $m$ is a number used to deal with cuts.
For every clause $n$, the one without cut is augmented with $allowed$($n$,0),
while those containing a cut somewhere in their body
are augmented with $allowed$($n$,1), $allowed$($n$,2), ..., and so on. 
Moreover, for every augmented clause as above, a fact ``$alt$($n$,$m$).''
is inserted in S, 
in order to implement an enumeration mechanism.
 
A simplified (but running) version  
of the learning algorithm is
reported below.  In the algorithm, the
output, if any, is the variable Trace containing the
list of the (numbers of the) clauses representing the learned program P. 
By using the backtracking mechanism of Prolog, 
more than one solution (trace) can be found.
We assume the two predicates $listpositive$ and $listnegative$
build a list of the given positive and negative examples, respectively.\\
 
%\renewcommand{\baselinestretch}{1.0}
\small
\normalsize
 
\noindent
consult(file\_containing\_the\_set\_of\_clauses\_S).\\
 
\noindent
allowed(X,0).\\
 
\noindent
marker(X) :- assert(trace(X)).\\
marker(X) :- retract(trace(X)), !, fail.\\
 
\noindent
main :- listpositive(Posexamplelist), tracer([],Posexamplelist,Trace).\\
 
\noindent
tracer(Covered,[Example$\mid$Cdr],Trace) :- Example, 
/$\star$ {\bf backtracking point 1} $\star$/\\
\hspace*{2.3in}setof(L,trace(L),Trace1),\\
\hspace*{2.3in}notneg(Trace1,[Example$\mid$Covered],Cdr),\\
\hspace*{2.3in}tracer([Example$\mid$Covered],Cdr,Trace).\\
tracer(\_,[],Trace) :- setof((I,J),allowed(I,J),Trace),
asserta((marker(X) :- true, !)).\\
 
\noindent
assertem([]).\\
assertem([I$\mid$Cdr]) :- alt(I,J), backassert(allowed(I,J)), assertem(Cdr).\\
 
\noindent
prep(T) :- retract(allowed(X,0)), assertem(T).\\
 
\noindent
backassert(X) :- assert(X).\\
backassert(X) :- retract(X), !, fail.\\
 
\noindent
resetallowed([]) :- !.\\
resetallowed(\_) :- abolish(allowed,2), assert(allowed(X,0)), !.\\
 
\noindent
notneg(T,Covered,Remaining) :- listnegative([]).\\
notneg(T,Covered,Remaining) :- listnegative(Negexamplelist),\\
\hspace*{2.3in}asserta((marker(X) :- true,!)),\\
\hspace*{2.3in} prep(T),
/$\star$ {\bf backtracking point 2} $\star$/\\
\hspace*{2.3in}trypos(Covered), trynegs(Negexamplelist),\\
\hspace*{2.3in}resetallowed(Remaining),\\
\hspace*{2.3in}retract((marker(X) :- true,!)).\\
notneg(T,Covered,Remaining) :- resetallowed(Remaining),\\
\hspace*{2.3in}retract((marker(X) :- true,!)), !, fail.\\
 
\noindent
trypos([Example$\mid$Cdr]) :-  Example, !, trypos(Cdr).\\
trypos([]) :- !.\\
 
\noindent
trynegs([Example$\mid$Cdr]) :-  Example,!,fail.\\
trynegs([Example$\mid$Cdr]) :-  trynegs(Cdr). \\
trynegs([]) :- !.\\
\noindent
 
 
%\renewcommand{\baselinestretch}{1.2} 
\small
\normalsize
 
\noindent
Actually, our complete implementation is more complex, also in order 
to achieve greater efficiency. The behavior of the learning
task is quite simple. Initially, the set S of clauses
is read into the Prolog interpreter, together
with the learning algorithm. Then the learning task can be started by calling
the predicate $main$. A list of the positive examples is formed and 
the $tracer$ procedure is called on that list. For every positive
example, $tracer$ calls the example itself, firing all the clauses
in S that may be resolved against that example. 
Observe that, initially, an $allowed$(X,0) predicate is asserted
in the database: in this way only clauses not
containing a cut are $allowed$ to be used (this is because clauses
with cut are employed only if some negative example is derived).
Then, a trace, if any,
of (the numbers associated to)
the clauses successfully used in the derivation of that example is built,
using the $setof$ predicate.
 
The trace is added to the traces
found for the previous examples, and the result
is checked against the set of
the negative examples calling the $notneg$ procedure. If $notneg$ does not
fail (i.e. no negative examples are covered by this trace) then a new positive
example is taken into consideration. Otherwise 
$notneg$ modifies the trace with cut and tests it again. If also this fails,
backtracking occurs and a new trace for the current example 
(and possibly for the previous ones) is searched for.
 
The $notneg$ procedure works as follows. First, only 
the clauses in the trace are $allowed$ to be 
checked against the negative examples, by 
retracting the $allowed$(X,0) clause and asserting an $allowed$($n$,0)
if the $n$-th clause (without cut) is in the trace.
This is done with the $prep$ and 
$assertem$ predicates. Then a list of the negative examples is formed
and we check if they can be derived from the clauses in the
trace. If at least one
negative example is covered, (i.e., if $trynegs$ fails) then we backtrack to
the $prep$ procedure (backtracking point 2)
where a clause of the trace is substituted
with an equivalent one but with cut inserted somewhere (or in a different
position). If no correct program can be found in such a way by trying all
possible alternatives (i.e. by using cut in all possible ways),
$notneg$ fails, and backtracking to backtracking point 1 occurs, where another
trace is searched for.
Otherwise, all clauses in S without cut are reactivated by asserting again 
$allowed$(X,0), and the next positive example is considered.
Note that $trypos$ is used in $notneg$ to verify if a modified trace still
derives the set of positive examples derived initially. The possibility
to substitute clauses in the current trace with others having cut inserted
somewhere is achieved through the $alt$ predicate in the $assertem$ procedure.
Finally, note that this simplified version of the learning procedure is not able
to generate and test for different orderings of clauses in a trace or for
different ordering of literals in each clause, nor to use
different orderings for the set of positive examples.
 
In order to derive all the positive examples before the check
against the negative ones (see subsection 4.4), 
we must
change the first clause of the $tracer$ procedure into:\\
 
\noindent
tracer([Pos1, ... ,Posn]):-Pos1, ... ,Posn,
                           setof(L,trace(L),T),
                           notneg(T).\\
 
                                 
\noindent
The actual implementation of the above induction procedure
is available through ftp. For further information contact
gunetti@di.unito.it.
 
 
%
\vskip 0.2in
\bibliographystyle{theapa}
%
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Aha, Ling, Matwin, \BBA\ Lapointe}{Aha
  et~al.}{1993}]{matwijcw93}
Aha, D., Ling, C., Matwin, S., \BBA\ Lapointe, S. \BBOP1993\BBCP.
\newblock \BBOQ {Learning Singly Recursive Relations from Small Datasets}\BBCQ\
\newblock In {\Bem Proceedings of the IJCAI-93 workshop on ILP}.

\bibitem[\protect\BCAY{Bergadano}{Bergadano}{1993a}]{bergtkde93}
Bergadano, F. \BBOP1993a\BBCP.
\newblock \BBOQ Inductive database relations\BBCQ\
\newblock {\Bem IEEE Transactions on Data and Knowledge Engineering}, {\Bem 5\/}(6).

\bibitem[\protect\BCAY{Bergadano}{Bergadano}{1993b}]{bergsigs93}
Bergadano, F. \BBOP1993b\BBCP.
\newblock \BBOQ {Test Case Generation by Means of Learning Techniques}\BBCQ\
\newblock In {\Bem Proceedings of ACM SIGSOFT-93}.

\bibitem[\protect\BCAY{Bergadano \BBA\ Gunetti}{Bergadano \BBA\
  Gunetti}{1993}]{bergijca93}
Bergadano, F.\BBACOMMA\  \BBA\ Gunetti, D. \BBOP1993\BBCP.
\newblock \BBOQ An interactive system to learn functional logic programs\BBCQ\
\newblock In {\Bem Proceedings of IJCAI-93}.

\bibitem[\protect\BCAY{Coelho \BBA\ Cotta}{Coelho \BBA\
  Cotta}{1988}]{prolbyex88}
Coelho, H.\BBACOMMA\  \BBA\ Cotta, J.~C. \BBOP1988\BBCP.
\newblock {\Bem Prolog by Example: how to learn teach and use it}.
\newblock Berlin: Springer-Verlag.

\bibitem[\protect\BCAY{Cohen}{Cohen}{1993}]{coheijcw93}
Cohen, W. \BBOP1993\BBCP.
\newblock \BBOQ {Rapid Prototyping of ILP Systems Using Explicit Bias}\BBCQ\
\newblock In {\Bem Proceedings of the IJCAI-93 workshop on ILP}.

\bibitem[\protect\BCAY{DeRaedt, Lavrac, \BBA\ Dzeroski}{DeRaedt
  et~al.}{1993}]{deraijca93}
DeRaedt, L., Lavrac, N., \BBA\ Dzeroski, S. \BBOP1993\BBCP.
\newblock \BBOQ Multiple predicate learning\BBCQ\
\newblock In {\Bem Proceedings of IJCAI-93}.

\bibitem[\protect\BCAY{Kietz \BBA\ Wrobel}{Kietz \BBA\
  Wrobel}{1991}]{wrobilpw91}
Kietz, J.~U.\BBACOMMA\  \BBA\ Wrobel, S. \BBOP1991\BBCP.
\newblock \BBOQ {Controlling the Complexity of Learning in Logic through
  Syntactic and Task-Oriented Models}\BBCQ\
\newblock In Muggleton, S.\BED, {\Bem Inductive Logic Programming}. London:
Academic Press.

\bibitem[\protect\BCAY{Lau \BBA\ Clement}{Lau \BBA\ Clement}{1993}]{lopstrwo93}
Lau, K.~K.\BBACOMMA\  \BBA\ Clement, T.\BEDS. \BBOP1993\BBCP.
\newblock {\Bem Logic Program Synthesis and Transformation}. Berlin: Springer-Verlag.

\bibitem[\protect\BCAY{Ling}{Ling}{1991}]{lingijca91}
Ling, X.~C. \BBOP1991\BBCP.
\newblock \BBOQ {Learning from Good Examples}\BBCQ\
\newblock In {\Bem Proceedings of IJCAI-91}.

\bibitem[\protect\BCAY{Muggleton}{Muggleton}{1991}]{muggilpw91}
Muggleton, S.\BED. \BBOP1991\BBCP.
\newblock {\Bem Inductive Logic Programming}.
\newblock London: Academic Press.

\bibitem[\protect\BCAY{Muggleton \BBA\ Feng}{Muggleton \BBA\
  Feng}{1990}]{muggaltc90}
Muggleton, S.\BBACOMMA\  \BBA\ Feng, C. \BBOP1990\BBCP.
\newblock \BBOQ {Efficient Induction of Logic Programs}\BBCQ\
\newblock In {\Bem Proceedings of the first conference on Algorithmic Learning Theory}.

\bibitem[\protect\BCAY{Quinlan}{Quinlan}{1990}]{quinmljo90}
Quinlan, R. \BBOP1990\BBCP.
\newblock \BBOQ {Learning Logical Definitions from Relations}\BBCQ\
\newblock {\Bem Machine Learning}, {\Bem 5}, 239--266.

\bibitem[\protect\BCAY{Rouveirol}{Rouveirol}{in press}]{rouvmljo94}
Rouveirol, C. (in press).
\newblock \BBOQ Flattening: a representation change for generalization\BBCQ\
\newblock {\Bem Machine Learning}.

\bibitem[\protect\BCAY{Russell}{Russell}{1988}]{russaaai88}
Russell, S. \BBOP1988\BBCP.
\newblock \BBOQ Tree-structured bias\BBCQ\
\newblock In {\Bem Proceedings of AAAI-88}.

\bibitem[\protect\BCAY{Shapiro}{Shapiro}{1983}]{shapbook83}
Shapiro, E.~Y. \BBOP1983\BBCP.
\newblock {\Bem Algorithmic Program Debugging}.
\newblock Cambridge, CA: MIT Press.

\end{thebibliography}
 
\end{document}


