\documentstyle[jair,twoside,11pt,theapa]{article} 
%\input epsf

\newcommand{\yy}[1]{{\it [#1]}}
\newcommand{\zz}[1]{}
\newcommand{\ct}[1]{[cite:#1]}
\newcommand{\shortct}[1]{[year:#1]}
\newcommand{\cut}[1]{}
\newcommand{\cd}[1]{{\it #1}}
\newcommand{\trm}[1]{{\em #1\/}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newenvironment{proof}{\noindent {\bf Proof:}}{\qed}
\newenvironment{lemmaproof}{\noindent {\bf Proof of lemma:}}{\qed}
%\newenvironment{example}{\begin{center}~\\%
%			 \begin{minipage}{0.9\textwidth}%
%			  \noindent {\bf Example.}}%
% 			{\end{minipage}~\\%
%			\end{center}}
%\newenvironment{example}{\noindent {\bf Example.}}{}
\newenvironment{example}{\begin{quote}{\bf Example.}}{\end{quote}}
\newenvironment{proofsketch}{\noindent {\bf Proof (sketch):}}{\qed}
\newcommand{\qed}{\hfill\rule{0.6em}{0.6em}\vspace{\baselineskip}}
\newenvironment{code}{\begin{tabbing}1234\=\kill}{\end{tabbing}}
\newenvironment{alg}{\begin{tabbing}1234\=1234\=1234\=1234\=1234\=\kill}{\end{tabbing}}
\newcommand{\predict}{\mbox{\sc PacPredict\/}}
\newcommand{\learn}{\mbox{\sc PacLearn\/}}
\newcommand{\ident}{\mbox{\sc Identify\/}}
\newcommand{\size}[1]{\mbox{$|\!|#1|\!|$}} % 
\newcommand{\ext}[2]{{\it ext}(#1,#2)}
\newcommand{\poly}{{\it poly}}
\newcommand{\llang}{\mbox{\sc Lang}}% 
\newcommand{\subcl}{\mbox{\sc Subclause}}% 
\newcommand{\dbset}{\mbox{${\cal DB}$}}
\newcommand{\dbj}[1]{\mbox{$#1$-${\cal DB}$}} % 
\newcommand{\decj}[1]{\mbox{$#1$-${\cal DEC}$}} % 
\newcommand{\db}{{\it DB}} % 
\newcommand{\dec}{{\it Dec}} % 
\newcommand{\decset}{\mbox{${\cal DEC}$}}
\newcommand{\detdec}{\mbox{${\cal D}$\it et${\cal DEC}$}}
\newcommand{\detdecj}[1]{\mbox{$#1$-${\cal D}$\it et${\cal DEC}$}} % 
\newcommand{\decsetj}[1]{\mbox{$#1$-${\cal DEC}$}} % 
\newcommand{\inp}{{\rm in}}
\newcommand{\outp}{{\rm out}}
\newcommand{\maxt}{{n_t}} % size of target
\newcommand{\maxi}{{n_e}} % size of instances
\newcommand{\maxb}{{n_b}} % size of background theory
\newcommand{\maxv}{{n_r}} % size of vocabulary
\newcommand{\deepen}{{\it DEEPEN}} 
\newcommand{\determ}[1]{\mbox{$#1$-{\sc Determinate}}}
\newcommand{\nrdepth}[1]{\mbox{$#1$-{\sc DepthNonRec}}}
\newcommand{\nrlocal}[1]{\mbox{$#1$-{\sc LocalNonRec}}}
\newcommand{\lrlocal}[1]{\mbox{$#1$-{\sc LocalLinRec}}}
\newcommand{\localprog}[3]%
    {\mbox{$#1$-{\sc Local}-$#2$-{\sc Rec}-$#3$-{\sc Clause}}}
\newcommand{\rdepth}[1]{\mbox{$#1$-{\sc DepthRec}}}
\newcommand{\lrdepthprog}[1]{\mbox{$#1$-{\sc DepthLinRecProg}}}
\newcommand{\lrdepth}[1]{\mbox{$#1$-{\sc DepthLinRec}}}
\newcommand{\krdepth}[2]{\mbox{$#1$-{\sc Depth}-$#2$-{\sc Rec}}}
\newcommand{\progtwodepth}[1]{\mbox{$#1$-{\sc Depth}-2-{\sc Clause}}}
\newcommand{\progdepth}[1]{\mbox{$#1$-{\sc Depth}-$n$-{\sc Clause}}}
\newcommand{\constrain}{{\it CONSTRAIN}} 
\newcommand{\clong}{{\it BOTTOM}^{*}}
\newcommand{\blong}{\hat{C}}
\newcommand{\maxlang}{\mbox{$kd$-\sc MaxRecLang}}
\newcommand{\clongd}[1]{{\it BOTTOM}_{#1}^{*}}

\newcommand{\finst}{{f_i}} % instance mapping
\newcommand{\fcon}{{f_c}} % concept mapping
\newcommand{\obar}[1]{\overline{#1}}  
\newcommand{\hcif}{\mbox{$\leftarrow$}}
\newcommand{\reduces}{\mbox{$\;\unlhd\;$}}
\newcommand{\resolves}{\mbox{$\;\sqcap\;$}}
\newcommand{\paramlang}[1]{\mbox{\sc #1}}
\newcommand{\dnf}{\paramlang{Dnf}}
\newcommand{\dfa}{\paramlang{Dfa}}
\newcommand{\monomial}{\paramlang{Monomial}}
\newcommand{\dlog}{\mbox{\sc DLog}}
\newcommand{\modes}[1]{{\it MODES}(#1)}
\newcommand{\act}{\mbox{\it active}}
\newcommand{\inact}{\mbox{\it inactive}}
\newcommand{\mesh}[4]{{\rm MESH}_{{#1},{#2}}({#3},{#4})}


\jairheading{2}{1995}{541-573}{9/94}{5/95}
\ShortHeadings{Pac-Learning Recursive Logic Programs: Negative Results}
{Cohen}
\firstpageno{541}

\begin{document}

\title{Pac-learning Recursive Logic Programs: \\ Negative Results}
\author{\name William W. Cohen	\email wcohen@research.att.com \\
	\addr 
	AT\&T Bell Laboratories\\
	600 Mountain Avenue, 
	Murray Hill, NJ 07974 USA}
	
\maketitle

\begin{abstract}
In a companion paper it was shown that the class of constant-depth
determinate $k$-ary recursive clauses is efficiently learnable.  In
this paper we present negative results showing that any natural
generalization of this class is hard to learn in Valiant's model of
pac-learnability.  In particular, we show that the following program
classes are cryptographically hard to learn: programs with an
unbounded number of constant-depth linear recursive clauses; programs
with one constant-depth determinate clause containing an unbounded
number of recursive calls; and programs with one linear recursive
clause of constant locality.  These results immediately imply the
non-learnability of any more general class of programs. We also show
that learning a constant-depth determinate program with either two
linear recursive clauses or one linear recursive clause and one
non-recursive clause is as hard as learning boolean DNF.  Together
with positive results from the companion paper, these negative results
establish a boundary of efficient learnability for recursive
function-free clauses.

\end{abstract}


\section{Introduction}

\trm{Inductive logic programming (ILP)} 
\cite{ILPBook92,MuggletonJLP94} is an active area of machine learning
research in which the hypotheses of a learning system are expressed
in a logic programming language.  While many different learning
problems have been considered in ILP, including some of great
practical interest 
\cite{MuggletonPE92,KingPNAS92,ZelleAAAI94,CohenAAAI94RC}, a class of
problems that is frequently considered is to reconstruct simple
list-processing or arithmetic functions from examples. A prototypical
problem of this sort might be learning to append two lists. Often,
this sort of task is attempted using only randomly-selected positive
and negative examples of the target concept.

Based on its similarity to the problems studied in the field of
automatic programming from examples
\cite{SummersJACM77,BiermannSMC78}, we will (informally) call this
class of learning tasks \trm{automatic logic programming} problems.
While a number of experimental systems have been built
\cite{QuinlanECML93,AhaECML94}, the experimental success in automatic logic
programming systems has been limited.  One common property of
automatic logic programming problems is the presence of
\trm{recursion}. The goal of this paper is to explore by analytic
methods the computational limitations on learning recursive programs
in Valiant's model of pac-learnability \citeyear{ValiantCACM84}. (In
brief, this model requires that an accurate approximation of the
target concept be found in polynomial time using a polynomial-sized
set of labeled examples, which are chosen stochastically.)  While it
will surprise nobody that such limitations exist, it is far from
obvious from previous research where these limits lie: there are few
provably fast methods for learning recursive logic programs, and even
fewer meaningful negative results.

The starting point for this investigation is a series of positive
learnability results appearing in a companion paper
\cite{CohenJAIREff}.  These results show that a single constant-depth
determinate clause with a constant number of ``closed'' recursive
calls is pac-learnable.  They also show that a two-clause
constant-depth determinate program consisting of one nonrecursive
clause and one recursive clause of the type described above is
pac-learnable, if some additional ``hints'' about the target concept
are provided.

In this paper, we analyze a number of generalizations of these
learnable languages. We show that that relaxing any of the
restrictions leads to difficult learning problems: in particular,
learning problems that are either as hard as learning DNF (an open
problem in computational learning theory), or as hard as cracking
certain presumably secure cryptographic schemes.  The main
contribution of this paper, therefore, is a delineation of the
boundaries of learnability for recursive logic programs.

The paper is organized as follows.  In Section~\ref{background sec} we
define the classes of logic programs and the learnability models that
are used in this paper.  In Section~\ref{crypto sec} we present
cryptographic hardness results for two classes of constant-depth
determinate recursive programs: programs with $n$ linear recursive
clauses, and programs with one $n$-ary recursive clause.  We also
analyze the learnability of clauses of constant locality, another
class of clauses that is pac-learnable in the nonrecursive case, and
show that even a single linearly recursive local clause is
cryptographically hard to learn.  We then turn, in Section~\ref{dnf
hardness sec}, to the analysis of even more restricted classes of
recursive programs.  We show that two different classes of
constant-depth determinate programs are prediction-equivalent to
boolean DNF: the class of programs containing a single linear
recursive clause and a single nonrecursive clause, and the class of
programs containing two linearly recursive clauses.  Finally, we
summarize the results of this paper and its companion, discuss related
work, and conclude.

Although this paper can be read independently of its companion paper
we suggest that readers planning to read both papers begin with the
companion paper \cite{CohenJAIREff}.

\section{Background} \label{background sec}

For completeness, we will now present the technical background needed
to state our results; however, aside from Sections~\ref{model sec} and
\ref{reduce sec}, which introduce polynomial predictability and
prediction-preserving reducibilities, respectively, this background
closely follows that presented in the companion paper
\cite{CohenJAIREff}.  Readers are encouraged to skip this section
if they are already familiar with the material.

\subsection{Logic Programs} \label{lp intro}

We will assume that the reader has some familiarity in logic
programming (such as can be obtained by reading one of the standard
texts \cite{Lloyd}.)  Our treatment of logic programs differs only in
that we will usually consider the body of a clause to be an ordered
set of literals.  We will also consider only logic programs without
function symbols---{\it i.e.},  programs written in Datalog.

The semantics of a Datalog program $P$ will be defined relative to to
a \trm{database}, $\db$, which is a set of ground atomic facts.  (When
convenient, we will also think of $\db$ as a conjunction of ground
unit clauses).  In particular, we will interpret $P$ and $\db$ as a
subset of the set of all \trm{extended instances}.  An \trm{extended
instance} is a pair $(f,D)$ in which the \trm{instance fact} $f$ is a
ground fact, and the \trm{description} $D$ is a set of ground unit
clauses.  An extended instance $(f,D)$ is covered by $(P,\db)$ iff
\[ \db \wedge D \wedge P \vdash f
\]

If extended instances are allowed, then function-free programs can
encode many computations that are usually represented with function
symbols.  For example, a function-free program that tests to see if a
list is the
\cd{append} of two other lists can be written as follows:
\begin{code}
{\bf Program $P$:}\\
append(Xs,Ys,Ys) $\hcif$ \\
\>null(Xs).\\
append(Xs,Ys,Zs) $\hcif$ \\
\>components(Xs,X,Xs1) $\wedge$\\
\>components(Zs,X,Zs1) $\wedge$\\
\>append(Xs1,Ys,Zs1).\\
~\\
{\bf Database $\db$:}\\
null(nil).
\end{code}
Here the predicate \cd{components(A,B,C)} means that
\cd{A} is a list with head \cd{B} and tail \cd{C};
thus an extended instance equivalent to 
\cd{append([1,2],[3],[1,2,3])} 
would have the instance fact $f=\cd{append(list12,list3,list123)}$
and a description containing these atoms:
\begin{code}
components(list12,1,list2), components(list2,2,nil),\\
components(list123,1,list23), components(list23,2,list3),\\
components(list3,3,nil)
\end{code}
The use of extended instances and function-free programs is closely
related to ``flattening'' \cite{RouveirolMLJ94,DeRaedtILP94}; some
experimental learning systems also impose a similar restriction
\cite{QuinlanMLJ90,PazzaniMLJ92}.  Another motivation for using extended
instances is technical. Under the (sometimes quite severe) syntactic
restrictions considered in this paper, there are often only a
polynomial number of possible ground facts---{\it i.e.}, the Herbrand
base is polynomial.  Hence if programs were interpreted in the usual
model-theoretic way it would be possible to learn a program equivalent
to any given target by simply memorizing the appropriate subset of the
Herbrand base.  However, if programs are interpreted as sets of
extended instances, such trivial learning algorithms become
impossible; even for extremely restricted program classes there are
still an exponential number of extended instances of size $n$.
Further discussion can be found in the companion paper
\cite{CohenJAIREff}.

Below we will define some of the terminology for logic programs that
will be used in this paper.

\subsubsection{Input/Output Variables}

If $A\hcif B_1\wedge\ldots\wedge B_r$ is an (ordered) definite clause,
then the \trm{input variables} of the literal $B_i$ are those
variables which also appear in the clause $A\hcif
B_1\wedge\ldots\wedge B_{i-1}$; all other variables appearing in $B_i$
are called \trm{output variables}.

\subsubsection{Types of Recursion}

A literal in the body of a clause is a
\trm{recursive literal} if it has the same predicate symbol and arity as the
head of the clause.  If every clause in a program has at most one
recursive literal, the program is \trm{linear recursive}. If every
clause in a program has at most $k$ recursive literals, the program is
\trm{$k$-ary recursive}.  If every recursive literal in a program contains
no output variables, the program is \trm{closed recursive.}

\subsubsection{Depth}

The \trm{depth} of a variable appearing in a (ordered) clause $A\hcif
B_1\wedge\ldots\wedge B_r$ is defined as follows.  Variables appearing
in the head of a clause have depth zero.  Otherwise, let $B_i$ be the
first literal containing the variable $V$, and let $d$ be the maximal
depth of the input variables of $B_i$; then the depth of $V$ is $d+1$.
The depth of a clause is the maximal depth of any variable in the
clause.

\subsubsection{Determinacy}

The literal $B_i$ in the clause $A\hcif B_1\wedge\ldots\wedge B_r$ is
\trm{determinate} iff for every possible substitution $\sigma$ that
unifies $A$ with some fact $e$ such that
\[ \db\vdash B_1\sigma\wedge\ldots\wedge B_{i-1}\sigma
\]
there is at most one maximal substitution $\theta$ so that $\db\vdash
B_i\sigma\theta$.  A clause is \trm{determinate} if all of its
literals are determinate.  Informally, determinate clauses are those
that can be evaluated without backtracking by a Prolog interpreter.

The term \trm{$ij$-determinate} \cite{MuggletonILP92} is sometimes
used for programs that are depth $i$, determinate, and contain
literals of arity $j$ or less.  A number of experimental systems
exploit restrictions associated with limited depth and determinacy
\cite{MuggletonILP92,QuinlanIMLW91,LavracAII92,CohenIJCAIWS93}. 
The learnability of constant-depth determinate clauses has also
received some formal study \cite{DzeroskiCOLT92,CohenAAAI93CryptLim}.

\begin{sloppypar}
\subsubsection{Mode Constraints and Declarations}

\trm{Mode declarations} are commonly used in analyzing Prolog code
or describing Prolog code; for instance, the mode declaration
``$\cd{components(+,-,-)}$'' indicates that the predicate
\cd{components} can be used when its first argument is an
input and its second and third arguments are outputs.  Formally, we
define the \trm{mode} of a literal $L$ appearing in a clause $C$ to be
a string $s$ such that the initial character of $s$ is the predicate
symbol of $L$, and for $j>1$ the $j$-th character of $s$ is a ``+'' if
the $(j-1)$-th argument of $L$ is an input variable and a ``$-$'' if
the $(j-1)$-th argument of $L$ is an output variable.  (This
definition assumes that all arguments to the head of a clause are
inputs; this is justified since we are considering only how clauses
behave in classifying extended instances, which are ground.) A
\trm{mode constraint} is a set of mode strings $R=\{s_1,\ldots,s_k\}$,
and a clause $C$ is said to
\trm{satisfy} a mode constraint $R$ for $p$ if for every literal
$L$ in the body of $C$, the mode of $L$ is in $R$.
\end{sloppypar}

We define a \trm{declaration} to be a tuple $(p,a',R)$ where $p$ is a
predicate symbol, $a'$ is an integer, and $R$ is a mode constraint.
We will say that a clause $C$ \trm{satisfies} a declaration if the
head of $C$ has arity $a'$ and predicate symbol $p$, and if for every
literal $L$ in the body of $C$ the mode of $L$ appears in $R$.

\subsubsection{Determinate Modes}

In a typical setting, that facts in the database $\db$ and extended
instances are not arbitrary: instead, they are representative of some
``real'' predicate, which may obey certain restrictions.  Let us
assume that all database and extended-instance facts will be drawn
>from some (possibly infinite) set ${\cal F}$.  Informally, a mode is
determinate if the input positions of the facts in ${\cal F}$
functionally determine the output positions.  Formally, if
$f=p(t_1,\ldots,t_k)$ is a fact with predicate symbol $p$ and
$p\alpha$ is a mode, then define
\( {\it inputs}(f,p\alpha) 
\) 
to be $\langle t_{i_1},\ldots,t_{i_k}\rangle$,
where ${i_1}$, \ldots, $i_k$ are the indices of $\alpha$ containing a 
``$+$'', and define
\( {\it outputs}(f,p\alpha) 
\) 
to be $\langle t_{j_1},\ldots,t_{j_l}\rangle$, where ${j_1}$, \ldots,
$j_l$ are the indices of $\alpha$ containing a ``$-$''. 
We define a mode string
$p\alpha$ for a predicate $p$ to be
\trm{determinate for ${\cal F}$} iff 
\[ \{\langle {\it inputs}(f,p\alpha),{\it outputs}(f,p\alpha)\rangle : 
	f\in{}{\cal F} \}
\] 
is a function. Any clause that satisfies a declaration
$\dec\in\detdec$ must be determinate.

The set of all declarations containing only modes determinate for
${\cal F}$ will be denoted $\detdec_{\cal F}$.  Since in this paper
the set ${\cal F}$ will be assumed to be fixed, we will generally omit
the subscript.

\subsubsection{Bounds on Predicate Arity}

We will use the notation $\dbj{a}$ for the set of all databases that
contain only facts of arity $a$ or less, and $\decj{a}$ for the set of
all declarations $(p,a',R)$ such that every string $s\in{}R$ is of
length $a+1$ or less.

\subsubsection{Size Measures}

The learning models presented in the following section will require
the learner to use resources polynomial in the size of its inputs.
Assuming that all predicates are arity $a$ or less for some constant
$a$ allows very simple size measures to be used.  In this paper, we
will measure the size of a database $\db$ by its cardinality; the size
of an extended instance $(f,D)$ by the cardinality of $D$; the size of
a declaration $(p,a',R)$ by the cardinality of $R$; and the size of a
clause $A\hcif{}B_1\wedge\ldots\wedge{}B_r$ by the number of literals
in its body.

\subsection{A Model of Learnability} \label{model sec}

\subsubsection{Preliminaries}

Let $X$ be a set. We will call $X$ the \trm{domain}, and call the
elements of $X$ \trm{instances}. Define a
\trm{concept} $C$ over $X$ to be a representation of some subset of
$X$, and define a {\em language} $\llang$ to be a set of concepts.  In
this paper, we will be rather casual about the distinction between a
concept and the set it represents; when there is a risk of confusion
we will refer to the set represented by a concept $C$ as the
\trm{extension of $C$}.  Two sets $C_1$ and $C_2$ with the same
extension are said to be \trm{equivalent}.  Define an \trm{example of
$C$} to be a pair $(e,b)$ where $b=1$ if $e\in C$ and $b=0$ otherwise.
If $D$ is a probability distribution function, a \trm{sample of $C$
>from $X$ drawn according to $D$} is a pair of multisets $S^{+},S^{-}$
drawn from the domain $X$ according to $D$, $S^+$ containing only
positive examples of $C$, and $S^-$ containing only negative ones.

Associated with $X$ and $\llang$ are two \trm{size complexity
measures}, for which we will use the following notation:
\begin{itemize} 
\item The size complexity of a concept $C\in\llang$ is written $\size{C}$.
\item The size complexity of an instance $e\in X$ is written $\size{e}$. 
\item If $S$ is a set, $S_n$ stands for the set of all
elements of $S$ of size complexity no greater than $n$.
For instance, $X_n=\{e\in X:\size{e}\leq n\}$ and
$\llang_n=\{C\in\llang:\size{C}\leq n\}$.
\end{itemize} 
We will assume that all size measures are polynomially related to the
number of bits needed to represent $C$ or $e$; this holds, for
example, for the size measures for logic programs and databases
defined above.

\subsubsection{Polynomial Predictability}

We now define polynomial predictability as follows.  A language
$\llang$ is \trm{polynomially predictable} iff there is an algorithm
\predict{} and a polynomial function
$m(\frac{1}{\epsilon},\frac{1}{\delta},\maxi,\maxt)$ so that for every
$\maxt>0$, every $\maxi>0$, every $C\in{\llang_{\maxt}}$, every
$\epsilon:0<\epsilon<1$, every $\delta:0<\delta<1$, and every
probability distribution function $D$,
\predict{} has the following behavior:
\begin{enumerate}
\item given a sample $S^{+},S^{-}$ of $C$ from $X_\maxi$ drawn
according to $D$ and containing at least
$m(\frac{1}{\epsilon},\frac{1}{\delta},\maxi,\maxt)$ examples,
\predict{}
outputs a hypothesis $H$ such that 
\[ Prob(D(H-C)+D(C-H)>\epsilon)<\delta 
\]
where the probability is taken over the possible samples $S^+$ and
$S^-$ and (if $\predict{}$ is a randomized algorithm) over any coin flips
made by $\predict{}$;
\item \predict{} runs in time polynomial in $\frac{1}{\epsilon}$,
$\frac{1}{\delta}$, $\maxi$, $\maxt$, and the number of
examples; and
\item The hypothesis $H$ can be evaluated in polynomial time.
\end{enumerate}

The algorithm \predict{} is called a \trm{prediction algorithm} for
$\llang$, and the function
$m(\frac{1}{\epsilon},\frac{1}{\delta},\maxi,\maxt)$ is called the
\trm{sample complexity} of $\predict$.
We will sometimes abbreviate ``polynomial predictability'' as 
``predictability''.  

The first condition in the definition merely states that the error
rate of the hypothesis must (usually) be low, as measured against the
probability distribution $D$ from which the training examples were
drawn.  The second condition, together with the stipulation that the
sample size is polynomial, ensures that the total running time of the
learner is polynomial.  The final condition simply requires that the
hypothesis be usable in the very weak sense that it can be used to
make predictions in polynomial time.  Notice that this is a {worst
case\/} learning model, as the definition allows an adversarial choice
of all the inputs of the learner.

\subsubsection{Relation to Other Models}

The model of polynomial predictability has been well-studied
\cite{PittJCSS90}, and is a weaker version of Valiant's
\citeyear{ValiantCACM84} criterion of \trm{pac-learnability}.
A language $\llang$ is \trm{pac-learnable} iff there is an algorithm
\learn{} so that
\begin{enumerate}
\item \learn{} satisfies all the requirements in the definition
of polynomial predictability, and
\item on inputs $S^+$ and $S^-$, \learn{}  always outputs a
hypothesis $H\in\llang$. 
\end{enumerate}
Thus if a language is pac-learnable it is predictable.

In the companion paper \cite{CohenJAIREff}, our positive results are
all expressed in the model of identifiability from equivalence
queries, which is strictly stronger than pac-learnability; that is,
anything that is learnable from equivalence queries is also
necessarily pac-learnable.\footnote{An equivalence query is a question
of the form ``is $H$ equivalent to the target concept?'' which is
answered with either ``yes'' or a counterexample.  Identification by
equivalence queries essentially means that the target concept can be
exactly identified in polynomial time using a polynomial of such
queries.} Since this paper contains only negative results, we will use
the the relatively weak model of predictability.  Negative results in
this model immediately translate to negative results in the stronger
models; if a language is not predictable, it cannot be pac-learnable,
nor identifiable from equivalence queries.

\subsubsection{Background Knowledge in Learning}

In a typical ILP system, the setting is slightly different, as the
user usually provides clues about the target concept in addition to
the examples, in the form of a database $\db$ of ``background
knowledge'' and a set of declarations.  To account for these
additional inputs it is necessary to extend the framework described
above to a setting where the learner accepts inputs other than
training examples.  Following the formalization used in the companion
paper
\cite{CohenJAIREff}, we will adopt the notion of a ``language
family''.

If $\llang$ is a set of clauses, $\db$ is a database and $\dec$ is a
declaration, we will define $\llang[\db,\dec]$ to be the set of all
pairs $(C,\db)$ such that $C\in\llang$ and $C$ satisfies $\dec$.
Semantically, such a pair will denote the set of all extended
instances $(f,D)$ covered by $(C,\db)$.  Next, if $\dbset$ is a set of
databases and $\decset$ is a set of declarations, then define
\[ \llang[\dbset,\decset] = 
     \{ \llang[\db,\dec] : \db\in\dbset\mbox{~and~}\dec\in\decset \}
\]
This set of languages is called a \trm{language family}.

We will now extend the definition of predictability queries to
language families as follows.  A language family
$\llang[\dbset,\decset]$ is {polynomially predictable} iff every
language in the set is predictable.  A language family
$\llang[\dbset,\decset]$ is
\trm{polynomially predictable} iff there is a
single algorithm $\ident(\db,\dec)$ that predicts every
$\llang[\db,\dec]$ in the family given $\db$ and $\dec$.

The usual model of polynomial predictability is worst-case over all
choices of the target concept and the distribution of examples.  The
notion of polynomial predictability of a language family extends this
model in the natural way; the extended model is also worst-case over
all possible choices for database $\db\in\dbset$ and $\dec\in\decset$.
This worst-case model may seem unintuitive, since one typically
assumes that the database $\db$ is provided by a helpful user, rather
than an adversary. However, the worst-case model is reasonable because
learning is allowed to take time polynomial in the size of smallest
target concept {\it in the set $\llang[\db,\dec]$}; this means that if
the database given by the user is such that the target concept cannot
be encoded succinctly (or at all) learning is allowed to take more
time.

Notice that for a language family $\llang[\db,\dec]$ to be
polynomially predictable, every language in the family must be
polynomially predictable.  Thus to show that a family is not
polynomially predictable it is sufficient to construct one language in
the family for which learning is hard.  The proofs of this paper will
all have this form.


\subsection{Prediction-Preserving Reducibilities} \label{reduce sec}

The principle technical tool used in our negative results in the
notion of \trm{prediction-preserving reducibility}, as introduced by
Pitt and Warmuth \citeyear{PittJCSS90}. Prediction-preserving
reducibilities are a method of showing that one language is no harder
to predict than another.  Formally, let $\llang_1$ be a language over
domain $X_1$ and $\llang_2$ be a language over domain $X_2$. We say
that \trm{predicting $\llang_1$ reduces to predicting $\llang_2$},
denoted $\llang_1\reduces\llang_2$, if there is a function
$\finst:X_1\rightarrow X_2$, henceforth called the
\trm{instance mapping}, and a function $\fcon:\llang_1\rightarrow
\llang_2$, henceforth called the \trm{concept mapping}, so that the
following all hold:
\begin{enumerate}
\item $x\in C$ \mbox{~if and only if~} $\finst(x) \in \fcon(C)$ ---
{\it i.e.}, concept membership is preserved by the mappings;
\item the size complexity of $\fcon(C)$ is polynomial in the 
size complexity of $C$---{\it i.e.}, the size of concept
representations is preserved within a polynomial factor;
\item $\finst(x)$ can be computed in polynomial time.
\end{enumerate}
Note that $\fcon$ need not be computable; also, since $\finst$ can be
computed in polynomial time, $\finst(x)$ must also preserve size
within a polynomial factor.

Intuitively, $\fcon(C_1)$ returns a concept $C_2\in\llang_2$ that will
``emulate'' $C_1$---{\it i.e.}, make the same decisions about concept
membership---on examples that have been ``preprocessed'' with the
function $\finst$.  If predicting $\llang_1$ reduces to predicting
$\llang_2$ and a learning algorithm for $\llang_2$ exists, then one
possible scheme for learning concepts from $\llang_1$ would be the
following. First, convert any examples of the unknown concept $C_1$
>from the domain $X_1$ to examples over the domain $X_2$ using the instance
mapping $\finst$.  If the conditions of the definition hold, then
since $C_1$ is consistent with the original examples, the concept
$\fcon(C_1)$ will be consistent with their image under $\finst$; thus
running the learning algorithm for $\llang_2$ should produce some
hypothesis $H$ that is a good approximation of $\fcon(C_1)$.  Of
course, it may not be possible to map $H$ back into the original
language $\llang_1$, as computing $\fcon^{-1}$ may be difficult or
impossible.  However, $H$ can still be used to predict membership in
$C_1$: given an example $x$ from the original domain $X_1$, one can
simply predict $x\in C_1$ to be true whenever $\finst(x) \in H$.

Pitt and Warmuth \citeyear{PittSCT88} give a more rigorous argument
that this approach leads to a prediction algorithm for $\llang_1$,
leading to the following theorem.

\begin{theorem}[Pitt and Warmuth] \label{pw thm}
Assume $\llang_1 \reduces \llang_2$.  Then 
if $\llang_1$ is {not}
polynomially predictable, $\llang_2$ is not polynomially
predictable.
\end{theorem}

\section{Cryptographic Limitations on Learning Recursive Programs}
\label{crypto sec}

Theorem~\ref{pw thm} allows one to transfer hardness results from one
language to another. This is useful because for a number of languages,
it is known that prediction is as hard as breaking cryptographic
schemes that are widely assumed to be secure.  For example, it is
known that predicting the class of languages accepted by deterministic
finite state automata is ``cryptographically hard'', as is the class
of languages accepted by log-space bounded Turing machines.

In this section we will make use of Theorem~\ref{pw thm} and previous
cryptographic hardness results to show that certain restricted classes
of recursive logic programs are hard to learn.

\subsection{Programs With $n$ Linear Recursive Clauses}

In a companion paper \cite{CohenJAIREff} we showed that a single
linear closed recursive clause was identifiable from equivalence
queries.  In this section we will show that a program with a
polynomial number of such clauses is not identifiable from equivalence
queries, nor even polynomially predictable.

\begin{sloppypar}
Specifically, let us extend our notion of a ``family of languages''
slightly, and let $\dlog[n,s]$ represent the language of log-space
bounded deterministic Turing machines with up to $s$ states accepting
inputs of size $n$ or less, with the usual semantics and complexity
measure.\footnote{{\it I.e.}, a machine represents the set of all inputs that
it accepts, and its complexity is the number of states.} Also let
$\lrdepthprog{d}$ denote the family of logic programs containing only
depth-$d$ linear closed recursive clauses, but containing any number
of such clauses.  We have the following result:
\end{sloppypar}

\begin{theorem} \label{lr det prog hard}
\begin{sloppypar}
For every $n$ and $s$, there exists a database $\db_{n,s}\in\dbj{1}$
and declaration $\dec_{n,s}\in\detdecj{1}$ of sizes polynomial in $n$
and $s$ such that
\[ \dlog[n,s]~\reduces~\lrdepthprog{1}[\db_{n,s},\dec_{n,s}]
\] 
Hence for $d\geq{}1$ and $a\geq{}1$,
$\lrdepthprog{d}[\dbset,\detdecj{a}]$ is not uniformly polynomially
predictable under cryptographic assumptions.\footnote{Specifically,
this language is not uniformly polynomially predictable unless all of
the following cryptographic problems can be solved in polynomial time:
solving the quadratic residue problem, inverting the RSA encryption
function, and factoring Blum integers.  This result holds because all
of these cryptographic problems can be reduced to learning DLOG Turing
machines \cite{KearnsSTOC89}.}
\end{sloppypar}
\end{theorem}

\begin{proof}
Recall that a log-space bounded Turing machine (TM) has an input tape
of length $n$, a work tape of length $\log_2{n}$ which initially
contains all zeros, and a finite state control with state set $Q$.  To
simplify the proof, we assume without loss of generality that the tape
and input alphabets are binary, that there is a single accepting state
$q_f\in Q$, and that the machine will always erase its work tape and
position the work tape head at the far left after it decides to accept
its input.

At each time step, the machine will read the tape squares under its
{input tape head} and {work tape head}, and based on these values and
its current state $q$, it will
\begin{itemize}
\item write either a 1 or a 0 on the work tape, 
\item shift the input tape head left or right,
\item shift the work tape head left or right, and
\item transition to a new internal state $q'$
\end{itemize}
A deterministic machine can thus be specified by a transition function 
\[ \delta : \{0,1\} \times \{0,1\} \times Q
   ~\longrightarrow~
	    \{0,1\} \times \{L,R\} \times \{L,R\} \times Q
\]

Let us define the \trm{internal configuration} of a TM to consist of
the string of symbols written on the worktape, the position of the
tape heads, and the internal state $q$ of the machine: thus a
configuration is an element of the set
\[ {\it CON} \equiv 
      \{0,1\}^{\log_2{n}} \times \{1,\ldots,\log_2{n}\} \times \{1,\ldots,n\} \times Q
\]
A simplified specification for the machine is the transition function
\[ \delta' : \{0,1\} \times {\it CON} \rightarrow {\it CON} 
\] 
where the component $\{0,1\}$ represents the contents of the input
tape at the square below the input tape head.  

Notice that for a machine whose worktape size is bounded by $\log{n}$,
the cardinality of {\it CON} is only $p=|Q|{n^2}\log_2{n}$, a
polynomial in $n$ and $s=|Q|$.  We will use this fact in our
constructions.

The background database $\db_{n,s}$ is as follows.  First, for
$i=0,\ldots,p$, an atom of the form
\cd{con$_i$(c$_i$)} is present. Each constant \cd{c$_i$} will represent
a different internal configuration of the Turing machine.  We will also 
arbitrarily select $c_1$ to represent the (unique) accepting
configuration, and add to $\db_{n,s}$ the atom
\cd{accepting(c$_{1}$)}.  Thus 
\[
\db_{n,s} \equiv       \{ \cd{con}_i(c_i) \}_{i=1}^{p} 
	 	  \cup \{ \cd{accepting}(c_1) \}
\]

Next, we define the instance mapping.  An instance in the Turing
machine's domain is a binary string $X=b_1\ldots b_n$; this is mapped
by $\finst$ to the extended instance $(f,D)$ where
\begin{eqnarray*}
f &\equiv& \cd{accepting(c_0)} \\
D &\equiv& \{ \cd{true_i} \}_{b_i\in X: b_i=1} ~~\cup~~
	    \{ \cd{false_i} \}_{b_i\in X: b_i=0}
\end{eqnarray*}
The description atoms have the effect of defining the predicate
\cd{true$_i$} to be true iff the $i$-th bit of $X$ is a ``1'', and
the defining the predicate \cd{false$_i$} to be true iff the $i$-th
bit of $X$ is ``0''.  The constant ${\it c}_0$ will represent the
start configuration of the Turing machine, and the predicate
\cd{accepting(C)} will be defined so that it is true iff the Turing machine
accepts input \cd{X} starting from state \cd{C}.

We will let $\dec_{n,s}=(\cd{accepting},1,R)$ where $R$ contains the modes
$\cd{con_i(+)}$ and $\cd{con_i(-)}$, for
$i=1,\ldots,p$; and $\cd{true_j}$ and $\cd{false_j}$ 
for $j=1,\ldots,n$.

Finally, for the concept mapping $\fcon$, let us assume some arbitrary
one-to-one mapping $\eta$ between the internal configurations of a
Turing machine $M$ and the predicate names
\cd{con$_0$},\ldots,\cd{con$_{p-1}$} such that 
the start configuration
\( (0^{\log_2{n}},1,q_0 ) \) 
maps to \cd{con$_0$} and the accepting configuration
\( ( 0^{\log_2{n}},1,q_f ) \) 
maps to \cd{con$_{1}$}.  We will construct the program $\fcon(M)$ as
follows.  For each transition $\delta'(1,c)\rightarrow c'$ in
$\delta'$, where $c$ and $c'$ are in ${\it CON}$, construct a clause
of the form
\begin{code}
\> accepting(C) $\hcif$ 
 con$_j$(C) $\wedge$ 
 true$_i$ $\wedge$ 
 con$_{j'}$(C1) $\wedge$ 
 accepting(C1).
\end{code}
where $i$ is the position of the input tape head which is encoded in
$c$, $\cd{con}_j=\eta(c)$, and $\cd{con}_{j'}=\eta(c')$.  
For each transition $\delta'(0,c)\rightarrow(c')$ in
$\delta'$ construct an analogous clause, in which
\cd{true$_i$} is replaced with \cd{false$_i$}.

Now, we claim that for this program $P$, the machine $M$ will accept
when started in configuration $c_i$ 
iff
\[ \db_{n,s}\wedge{}D\wedge{}P \vdash \cd{accepting(c_i)} 
\]
and hence that this construction preserves concept membership.  This
is perhaps easiest to see by considering the action of a top-down
theorem prover when given the goal $\cd{accepting(C)}$: the sequence
of subgoals $\cd{accepting(c_i)}$, $\cd{accepting(c_{i+1})}$, \ldots
generated by the theorem-prover precisely parallel the sequence of
configurations $c_i$, \ldots entered by the Turing machine.

It is easily verified that the size of this program is polynomial in
$n$ and $s$, and that the clauses are linear recursive, determinate, and
of depth one, completing the proof.
\end{proof}

There are number of ways in which this result can be strengthened.
Precisely the same construction used above can be used to reduce the
class of {nondeterministic} log-space bounded Turing machines to the
constant-depth determinate linear recursive programs.  Further, a
slight modification to the construction can be used to reduce the
class of log-space bounded alternating Turing machines
\cite{ChandraJACM81} to constant-depth determinate 2-ary recursive
programs.  The modification is to emulate configurations corresponding
to universal states of the Turing machine with clauses of the form
\begin{code}
accepting(C) $\hcif$ \\
\> con$_j$(C) $\wedge$ true$_i$ $\wedge$ \\
\> con$_{j1'}$(C1) $\wedge$ accepting(C1) $\wedge$ \\
\> con$_{j2'}$(C2) $\wedge$ accepting(C2).
\end{code}
where $\cd{con_{j1'}}$ and $\cd{con_{j2'}}$ are the two successors to
the universal configuration $\cd{con_j}$.  This is a very strong
result, since log-space bounded alternating Turing machines are known
to be able to perform every polynomial-time computation.

\subsection{Programs With One $n$-ary Recursive Clause}

We will now consider learning a single recursive clause with arbitrary
closed recursion.  Again, the key result of this section is an
observation about expressive power: there is a background database
that allows every log-space deterministic Turing machine $M$ to be
emulated by a single recursive constant-depth determinate clause.
This leads to the following negative predictability result.

\begin{theorem} \label{det clause hard}
For every $n$ and $s$, there exists a database $\db_{n,s}\in\dbj{3}$
and declaration $\dec_{n,s}\in\detdecj{3}$ of sizes polynomial in $n$
and $s$ such that
\[ \dlog[n,s]~\reduces~\rdepth{3}[\db_{n,s},\dec_{n,s}]
\] Hence for $d\geq{}3$ and $a\geq{}3$, $\rdepth{d}[\db_n,\detdecj{a}]$
is not uniformly polynomially predictable under cryptographic assumptions.
\end{theorem}

\begin{proof}
Consider a DLOG machine $M$.  As in the proof of Theorem~\ref{lr det
prog hard}, we assume without loss of generality that the tape
alphabet is $\{0,1\}$, that there is a unique starting configuration
$c_0$, and that there is a unique accepting configuration $c_1$. We
will also assume without loss of generality that there is a unique
``failing'' configuration $c_{fail}$; and that there is exactly one
transition of the form
\[ \delta'(b,c_j) \rightarrow c_j'
\]
for every combination of $i\in\{1,\ldots,n\}$, $b\in\{0,1\}$, and
$c_j\in CON-\{c_1,c_{fail}\}$.  Thus on input $X=x_1\ldots x_n$ the
machine $M$ starts with CONFIG=$c_0$, then executes transitions until
it reaches CONFIG=$c_1$ or CONFIG=$c_{fail}$, at which point $X$ is
accepted or rejected (respectively).  We will use $p$ for the number
of configurations. (Recall that $p$ is polynomial in $n$ and $s$.)

To emulate $M$, we will convert an example $X=b_1\ldots b_n$ into the
extended instance $\finst(X)=(f,D)$ where
\begin{eqnarray*}
 f &\equiv& \cd{accepting(c_0)}  \\
 D &\equiv& \{ \cd{bit}_i(b_i) \}_{i=1}^{n}
\end{eqnarray*}
Thus the predicate $\cd{bit}_i(X)$ binds $X$ to the $i$-th bit of the
TM's input tape. We also will define the following predicates in the
background database $\db_{n,s}$.
\begin{itemize}
\item  For every possible $b\in\{0,1\}$ and $j:1\leq j \leq
p(n)$, the predicate \cd{status$_{b,j}$(B,C,Y)} will be defined so that
given bindings for variables $B$ and $C$,
\cd{status$_{b,j}$(B,C,Y)} will fail if $C=c_{fail}$; otherwise it will
succeed, binding $Y$ to $\act$ if $B=b$ and $C=c_j$ and binding $Y$ to
$\inact$ otherwise.  
\item  For $j:1\leq j \leq p(n)$, the predicate
\cd{next$_{j}$(Y,C)} will succeed iff $Y$ can be bound to either 
$\act$ or $\inact$.  If $Y=\active$, then $C$ will be bound to $c_j$;
otherwise, $C$ will be bound to the accepting configuration $c_1$.
\item The database also contains the fact $\cd{accepting(c_1)}$.  
\end{itemize}
It is easy to show that the size of this database is polynomial 
in $n$ and $s$.

\begin{sloppypar}
The declaration $\dec_{n,s}$ is defined to be $(\cd{accepting},1,R)$ where
$R$ includes the modes $\cd{status}_{bj}(+,+,-)$, $\cd{next}_j(+,-)$,
and $\cd{bit}_i(-)$ for $b\in\{0,1\}$, $j=1,\ldots,p$, and
$i=1,\ldots,n$.
\end{sloppypar}

Now, consider the transition rule $\delta'(b,c_j)\rightarrow{}c_j'$,
and the corresponding conjunction
\begin{code}
{TRANS}$_{ibj}$ $\equiv$
         bit$_i$(B$_{ibj}$) $\wedge$ 
	 status$_{b,j}$(C,B$_{ibj}$,Y$_{ibj}$) $\wedge$ 
	 next$_{j'}$(Y$_{ibj}$,C1$_{ibj}$) $\wedge$ 
	 accepting(C1$_{ibj}$)
\end{code}
Given $\db_{n,s}$ and $D$, and assuming that $C$ is bound to some
configuration $c$, this conjunction will fail if $c=c_{fail}$.  It
will succeed if $x_i\not=b$ or $c\not=c_j$; in this case
\cd{Y}$_{ibj}$ will be bound to \inact{},
\cd{C1}$_{ibj}$ will be bound to $c_1$, and the recursive call
succeeds because \cd{accepting(c$_1$)} is in $\db_{n,s}$. Finally, if
$x_i=b$ and $c=c_j$, {TRANS}$_{ibj}$ will succeed only if the atom
\cd{accepting(c$_{j'}$)} is provable; in this case, \cd{Y}$_{ibj}$
will be bound to \act{} and \cd{C1}$_{ibj}$ will be bound to $c_{j'}$.

>From this it is clear that the clause $\fcon(M)$ below
\[ {\rm accepting(C)} \leftarrow 
	 \bigwedge_{\begin{array}{c}
			{}_{ i\in\{1,\ldots,n\},~{ b\in\{0,1\}}}\\
	 		{}_{ j\in\{1,\ldots,p\}}
		    \end{array}} 
	{\rm TRANS}_{ibj}
\]
will correctly emulate the machine $M$ on examples that have been
preprocessed with the function $\finst$ described above.  Hence this
construction preserves concept membership.  It is also easily verified
that the size of this program is polynomial in $n$ and $s$, and that
the clause is determinate and of depth three.
\end{proof}

\subsection{One $k$-Local Linear Closed Recursive Clause}
\label{klocal sec}

So far we have considered only one class of extensions to the positive
result given in the companion paper \cite{CohenJAIREff}---namely,
relaxing the restrictions imposed on the recursive structure of the
target program.  Another reasonable question to ask is if linear
closed recursive programs can be learned without the restriction of
constant-depth determinacy.

In earlier papers
\cite{CohenAAAI93CryptLim,CohenAAAI94Local,CohenNonRecJnl93} we have
studied the conditions under which the constant-depth determinacy
restriction can be relaxed while still allowing learnability for
{nonrecursive\/} clauses.  It turns out that most generalizations of
constant-depth determinate clauses are not predictable, even without
recursion.  However, the language of nonrecursive clauses of constant
\trm{locality} is a pac-learnable generalization of constant-depth
determinate clauses.  Below, we will define this language, summarize
the relevant previous results, and then address the question of the
learnability of recursive local clauses.

Define a variable $V$ appearing in a clause $C$ to be \trm{free} if it
appears in the body of $C$ but not the head of $C$.  Let $V_1$ and
$V_2$ be two free variables appearing in a clause.  $V_1$
\trm{touches} $V_2$ if they appear in the same literal, and $V_1$
\trm{influences} $V_2$ if it either touches $V_2$, or if it touches some
variable $V_3$ that influences $V_2$.  The \trm{locale} of a free
variable $V$ is the set of literals that either contain $V$, or that
contain some free variable influenced by $V$.  Informally, variable
$V_1$ influences variable $V_2$ if the choice of a binding for $V_1$
can affect the possible choices of bindings for $V_2$.

The \trm{locality} of a clause is the size of its largest locale.  Let
$\nrlocal{k}$ denote the language of nonrecursive clauses with
locality $k$ or less.  (That is, $\nrlocal{k}$ is the set of logic
programs containing a single nonrecursive $k$-local clause.) The
following facts are known
\cite{CohenNonRecJnl93}:
\begin{itemize}
\item For fixed $k$ and $a$, the language family 
$\nrlocal{k}[\dbj{a},\decsetj{a}]$ is uniformly pac-learnable.
\item For every constant $d$, every constant $a$,
every database $\db\in\dbj{a}$, every declaration 
$\dec\in\detdecj{a}$, and every clause $C\in\nrdepth{d}[\db,\dec]$,
there is an equivalent 
clause $C'$ in $\nrlocal{k}[\db,\dec]$ of size bounded
by $k\size{C}$, where $k$ is a function only of $a$ and $d$
(and hence is a constant if $d$ and $a$ are also constants.)

Hence 
\[ \nrlocal{k}[\dbset,\decsetj{a}]
\] 
is a pac-learnable generalization of 
\[ \nrdepth{d}[\dbset,\detdecj{a}]
\]
\end{itemize} 

It is thus plausible to ask if recursive programs of $k$-local clauses
are pac-learnable.  Some facts about the learnability of $k$-local
programs follow immediately from previous results. For example, an
immediate consequence of the construction of Theorem~\ref{lr det prog
hard} is that programs with a polynomial number of linear recursive
$k$-local clauses are not predictable for $k\geq{}2$.  Similarly,
Theorem~\ref{det clause hard} shows that a single recursive $k$-local
clause is not predictable for $k\geq{}4$.

It is still reasonable to ask, however, if the positive result for
bounded-depth determinate recursive clauses \cite{CohenJAIREff} can be
extended to $k$-ary closed recursive $k$-local clauses.
Unfortunately, we have the following negative result, which shows that
even linear closed recursive clauses are not learnable.

\begin{theorem} \label{klocal hard}
Let $\dfa[s]$ denote the language of deterministic finite automata
with $s$ states, and let $\lrlocal{k}$ be the set of linear closed
recursive $k$-local clauses.  For any constant $s$ there exists a
database $\db_s\in\dbj{3}$ and a declaration $\dec_s\in\decsetj{3}$,
both of size polynomial in $s$, such that
\[ \dfa[s]\reduces\lrlocal{3}[\db_s,\dec_s]
\] 
Hence for $k\geq{}3$ and $a\geq{}3$, $\lrlocal{k}[\dbj{a},\dec]$ is
not uniformly polynomially predictable under cryptographic
assumptions.
\end{theorem}

\begin{proof} Following Hopcroft and Ullman \citeyear{HopcroftUllman}
we will represent a DFA $M$ over the alphabet $\Sigma$ as a tuple
$(q_0,Q,F,\delta)$ where $q_0$ is the initial state, $Q$ is the set of
states, $F$ is the set of accepting states, and
$\delta:Q\times\Sigma\rightarrow{}Q$ is the transition function (which
we will sometimes think of as a subset of $Q\times\Sigma\times{}Q$).
To prove the theorem, we need to construct a database $\db_s$ of size
polynomial in $s$ such that every $s$-state DFA can be emulated by a
linear recursive $k$-local clause over $\db_s$.

\begin{figure}
\centerline{\input{hacked-dfa}}
\caption{How a DFA is modified before emulation with a local clause}
\label{dfa-form}
\end{figure}

Rather than directly emulating $M$, it will be convenient to emulate
instead a modification of $M$.  Let $\hat{M}$ be a DFA with state set
$\hat{Q}\equiv{}Q\cup\{q_{(-1)},q_e,q_f\}$, where $q_{(-1)}$, $q_e$
and $q_f$ are new states not found in $Q$.  The initial state of
$\hat{M}$ is $q_{(-1)}$.  The only final state of $\hat{M}$ is $q_f$.
The transition function of $\hat{M}$ is
\[ \hat{\delta}\equiv\delta\cup\{(q_{(-1)},a,q_0),(q_e,c,q_f)\}
	\cup~\bigcup_{q_i\in{}F} \{(q_i,b,q_e)\}
\] 
where $a$, $b$, and $c$ are new letters not in $\Sigma$.  Note that
$\hat{M}$ is now a DFA over the alphabet $\Sigma\cup\{a,b,c\}$, and,
as described, need not be a complete DFA over this alphabet.  (That
is, there may be pairs $(q_i,a)$ such that $\hat{\delta}(q_i,a)$ is
undefined.)  However, $\hat{M}$ can be easily made complete by
introducing an additional rejecting state $q_r$, and making every
undefined transition lead to $q_r$. More precisely, let $\delta'$ be
defined as
\[ \delta' \equiv \hat{\delta} \cup \{ (q_i,x,q_r) ~|~
	q_i\in\hat{Q}~\wedge{}~x\in\Sigma\cup\{a,b,c\}~\wedge{}~
	(\not\exists{}q_j:(q_i,x,q_j)\in\hat\delta) \}
\]  
Thus $M'=(q_{(-1)},\hat{Q}\cup\{q_r\},\{q_f\},\delta')$ is a
``completed'' version of $\hat{M}$, with $Q'=\hat{Q}\cup\{q_r\}$.  We
will use $M'$ in the construction below; we will also let
$Q'=\hat{Q}\cup\{q_r\}$ and $\Sigma'=\Sigma\cup\{a,b,c\}$.  

Examples of $M$, $\hat{M}$ and $M'$ are shown in
Figure~\ref{dfa-form}.  Notice that aside from the arcs into and out
of the rejecting state $q_r$, the state diagram of $M'$ is nearly
identical to that of $M$. The differences are that in $M'$ there is a
new initial state $q_{(-1)}$ with a single outgoing arc labeled $a$ to
the old initial state $q_0$; also every final state of $M$ has in $M'$
an outgoing arc labeled $b$ to a new state $q_e$, which in turn has a
single outgoing arc labeled $c$ to the final state $q_f$.  It is easy
to show that
\[ x\in{}L(M) \mbox{~iff~} axbc\in{}L(M')
\] 

Now, given a set of states $Q'$ we define a database $\db$
that contains the following predicates:
\begin{itemize}
\item \cd{arc$_{q_i,\sigma,q_j}$(S,X,T)} is true for any $S\in{}Q'$, 
any $T\in{}Q'$, and any $X\in\Sigma'$, unless $S=q_i$, $X=\sigma$, and
$T\not=q_j$.
\item \cd{state(S)} is true for any $S\in{}Q'$.
\item \cd{accept(c,\cd{nil},$q_e$,$q_f$)} is true.
\end{itemize} 
As motivation for the \cd{arc} predicates, observe that in emulating
$M'$ it is clearly useful to be able to represent the transition
function $\delta'$.  The usefulness of the \cd{arc} predicates is that
any transition function $\delta'$ can be represented using a
conjunction of \cd{arc} literals. In particular, the conjunction
\[  \bigwedge_{(q_i,\sigma,q_j)\in\delta'} \cd{arc}_{q_i,\sigma,q_j}(S,X,T)
\]
succeeds when $\delta'(S,X)=T$, and fails otherwise.

Let us now define the instance mapping $\finst$ as 
$\finst(x)=(f,D)$ where
\[ f=	\cd{accept}(a,xbc,q_{(-1)},q_0)
\]
and $D$ is a set of facts that defines the \cd{components} relation
on the list that corresponds to the string $xbc$.  In other words,
if $x=\sigma_1\ldots\sigma_n$, then $D$ is the set
of facts
\begin{code}
\>components($\sigma_1\ldots\sigma_n{}bc,\sigma_1,\sigma_2\ldots{}\sigma_n{}bc$)\\
\>components($\sigma_2\ldots\sigma_n{}bc,\sigma_2,\sigma_3\ldots{}\sigma_n{}bc$)\\
\>$\vdots$\\
\>components(c,c,nil)
\end{code} 

\begin{sloppypar}
The declaration $\dec_n$ will be $\dec_n=(\cd{accept},4,R)$ where $R$
contains the modes $\cd{components}(+,-,-)$, $\cd{state}(-)$, and
$\cd{arc}_{q_i,\sigma,q_j}(+,+,+)$ for $q_i$, $q_j$ in $Q'$,
and $\sigma\in\Sigma'$.
\end{sloppypar}

Finally, define the concept mapping $\fcon(M)$ for a machine $M$
to be the clause
\begin{code}
accept(X,Ys,S,T) $\hcif$ \\
\> $\bigwedge_{(q_i,\sigma,q_j)\in\delta'}$ arc$_{q_i,\sigma,q_j}$(S,X,T)  \\
\> $\wedge$ 
   components(Ys,X1,Ys1) $\wedge$ state(U) $\wedge$ accept(X1,Ys1,T,U).
\end{code} 
where $\delta'$ is the transition function for the corresponding
machine $M'$ defined above.  It is easy to show this construction is
polynomial.

In the clause $X$ is a letter in $\Sigma'$, \cd{Ys} is a list of such
letters, and $S$ and $T$ are both states in $Q'$.  The intent of the
construction is that the predicate \cd{accept} will succeed exactly
when (a) the string \cd{XYs} is accepted by $M'$ when $M'$ is started
in state $S$, and (b) the first action taken by $M'$ on the string
\cd{XYs} is to go from state $S$ to state $T$.

Since all of the initial transitions in $M'$ are from $q_{(-1)}$ to
$q_0$ on input $a$, then if the predicate \cd{accept} has the claimed
behavior, clearly the proposed mapping satisfies the requirements of
Theorem~\ref{pw thm}.  To complete the proof, therefore, we must now
verify that the predicate \cd{accept} succeeds iff \cd{XYs} is
accepted by $M'$ in state $S$ with an initial transition to $T$.

>From the definition of DFAs the string \cd{XYs} is accepted by $M'$
in state $S$ with an initial transition to $T$ iff one of the
following two conditions holds.
\begin{itemize}
\item $\delta'(S,X)=T$, 
\cd{Ys} is the empty string and $T$ is a final state
of $M'$, or;

\item $\delta'(S,X)=T$, 
\cd{Ys} is a nonempty string (and hence has some head $X1$ and some
tail \cd{Ys1}) and \cd{Ys1} is accepted by $M'$ in state $T$, with any
initial transition.
\end{itemize} 

The base fact
\cd{accept(c,\cd{nil},$q_e$,$q_f$)} succeeds precisely when the first
case holds, since in $M'$ this transition is the only one to a final
state. In the second case, the conjunction of the \cd{arc} conditions
in the $\fcon(M)$ clause succeeds exactly when $\delta(S,X)=T$ (as
noted above).  Further the second conjunction in the clause can be
succeeds when \cd{Ys} is a nonempty string with head $X1$ and tail
\cd{Ys1} and \cd{X1Ys1} is accepted by $M'$ in state $T$ with initial
transition to any state $U$, which corresponds exactly to the second
case above.

Thus concept membership is preserved by the mapping.  This completes
the proof.
\end{proof}

\section{DNF-Hardness Results for Recursive Programs} 
\label{dnf hardness sec}

To summarize previous results for determinate clauses, it was shown
that while a single $k$-ary closed recursive depth-$d$ clause is
pac-learnable \cite{CohenJAIREff}, a set of $n$ linear closed
recursive depth-$d$ clauses is not; further, even a single $n$-ary
closed recursive depth-$d$ clauses is not pac-learnable.  There is
still a large gap between the positive and negative results, however:
in particular, the learnability of recursive programs containing a
constant number of $k$-ary recursive clauses has not yet been
established.

In this section we will investigate the learnability of these classes
of programs.  We will show that programs with either two linear closed
recursive clauses or one linear closed recursive clause and one base
case are as hard to learn as boolean functions in disjunctive normal
form (DNF).  The pac-learnability of DNF is a long-standing open
problem in computational learning theory; the import of these results,
therefore, is that establishing the learnability of these classes will
require some substantial advance in computational learning theory.

\subsection{A Linear Recursive Clause Plus a Base Clause}
\label{rec base sec}

Previous work has established that two-clause constant-depth
determinate programs consisting of one linear recursive clause and one
nonrecursive clause can be identified, given two types of oracles: the
standard equivalence-query oracle, and a ``{basecase} oracle'
\cite{CohenJAIREff}.  (The basecase oracle determines if an example
is covered by the nonrecursive clause alone.) In this section we will
show that in the absence of the {basecase} oracle, the learning
problem is as hard as learning boolean DNF.

In the discussion below, $\dnf[n,r]$ denotes the language of $r$-term
boolean functions in disjunctive normal form over $n$ variables.

\begin{theorem} \label{force2 neg res}
Let $\progtwodepth{d}$ be the set of 2-clause programs consisting of
one clause in $\lrdepth{d}$ and one clause in $\nrdepth{d}$.  Then for
any $n$ and any $r$ there exists a database $\db_{n,r}\in\dbj{2}$ and
a declaration $\dec_{n,r}\in\decsetj{2}$, both of sizes polynomial in
$n$ and $r$, such that
\[ \dnf[n,r]\reduces\progtwodepth{1}[\db_{n,r},\dec_{n,r}]
\]
Hence for $a\geq{}2$ and $d\geq{}1$ the language family
\( \progtwodepth{d}[\dbset,\detdecj{a}]
\) 
is uniformly polynomially predictable only if DNF is polynomially
predictable.
\end{theorem}

\begin{proof} We will produce a $\db_{n,r}\in\dbset$ and 
$\dec_{n,r}\in\detdecj{2}$ such that predicting DNF can be reduced to
predicting $\progtwodepth{1}[\db_{n,r},\dec_{n,r}]$.  The construction
makes use of a trick first used in Theorem~3 of
\cite{CohenAAAI93CryptLim}, in which a DNF formula is emulated by a
conjunction containing a single variable $Y$ which is existentially
quantified over a restricted range.

We begin with the instance mapping $\finst$.  
An assignment $\eta=b_1\ldots{}b_n$
will be converted to the extended instance $(f,D)$ where
\begin{eqnarray*}
f &\equiv& p(1) \\
D &\equiv& \{ \cd{bit}_i(b_i) \}^{n}_{i=1} 
\end{eqnarray*}
Next, we define the database $\db_{n,r}$ to contain the
binary predicates \cd{true$_1$}, \cd{false$_1$},
\ldots, \cd{true$_r$}, \cd{false$_r$} which behave as follows:
\begin{itemize}
\item \cd{true$_i$(X,Y)} succeeds if $X=1$, 
or if $Y\in\{1,\ldots,r\}-\{i\}$.
\item \cd{false$_i$(X,Y)} succeeds if $X=0$,
or if $Y\in\{1,\ldots,r\}-\{i\}$. 
\end{itemize}
Further, $\db_{n,r}$ contains facts that define the predicate
\cd{succ(Y,Z)} to be true whenever $Z=Y+1$, and both $Y$ and $Z$ are
numbers between 1 and $r$.  Clearly the size of $\db_{n,r}$ is
polynomial in $r$.


Let $\dec_{n,r}=(p,1,R)$ where $R$ contains the modes $\cd{bit}_i(-)$,
for $i=1,\ldots,n$; $\cd{true}_j(+,+)$ and $\cd{false}_j(+,+)$, for
$j=1,\ldots,r$, and $\cd{succ}(+,-)$.

Now let $\phi$ be an $r$-term DNF formula
$\phi=\vee_{i=1}^r\wedge_{j=1}^{s_i} l_{ij}$ over the variables
$v_1,\ldots,v_n$. We may assume without loss of generality that $\phi$
contains exactly $r$ terms, since any DNF formula with fewer than $r$
terms can be padded to exactly $r$ terms by adding terms of the form
$v_1\obar{v_1}$.  We now define the concept mapping $\fcon(\phi)$ to
be the program $C_R,C_B$ where $C_R$ is the linear recursive depth 1
determinate clause
\[ p(Y) \hcif \cd{succ}(Y,Z)\wedge{}p(Z)
\]
and $C_B$ is the nonrecursive depth 1 determinate clause
\[ p(Y) \hcif \bigwedge_{k=1}^n \cd{bit}_k(X_k)
		      ~\wedge~ \bigwedge_{i=1}^r \bigwedge_{j=1}^{s_i}
					B_{ij}
\] 
where $B_{ij}$ is defined as follows:
\[ B_{ij} \equiv 
      \left\{
	\begin{array}{ll}
	\mbox{\cd{true$_i$(X$_{k}$,Y)}} & \mbox{if $l_{{ij}}=v_k$} \\
	\mbox{\cd{false$_i$(X$_{k}$,Y)}} & \mbox{if $l_{{ij}}=\obar{v_k}$}
	\end{array}
       \right.
\]

\begin{figure}[tb]
%\hrule
\begin{tabbing}12\=12\=\kill
{\bf Background database:}\\
\>for $i=1,\ldots,r$\\
\> \> true$_i(b,y)$  ~\=for all $b,y : b=1$ 
	or $y\in\{1,\ldots,r\}$ but $y\not=i$\\
\> \> false$_i(b,y)$  \>for all $b,y : b=0$ 
	or $y\in\{1,\ldots,r\}$ but $y\not=i$\\
\>succ(y,z) \>\>if $z=y+1$ and $y\in\{1,\ldots,r\}$ 
			   and $z\in\{1,\ldots,r\}$ \\
\ \\
{\bf DNF formula:} ~~ ($v_1\wedge\obar{v_3}\wedge v_4) ~\vee~ 
  (\obar{v_2}\wedge\obar{v_3}) ~\vee~ 
  (v_1\wedge\obar{v_4}$) \\
\ \\
{\bf Equivalent program:} \\
\>p(Y) \hcif succ(Y,Z)$\wedge{}$p(Z).\\
\>p(Y) \hcif %\\
%\>\>   
             bit$_1$(X$_1$) $\wedge$ bit$_2$(X$_2$) 
		$\wedge$ bit$_3$(X$_3$) $\wedge$ bit$_4$(X$_4$) $\wedge$ \\
\>\>   true$_1$(X$_1$,Y) $\wedge$ false$_1$(X$_3$,Y) $\wedge$ true$_1$(X$_4$,Y) $\wedge$ \\
\>\>   false$_2$(X$_2$,Y) $\wedge$ false$_2$(X$_3$,Y)$\wedge$ \\
\>\>   true$_3$(X$_1$,Y) $\wedge$ false$_3$(X$_4$,Y).\\
\ \\
{\bf Instance mapping:}~~
  $\finst(1011) = (p(1),\{\cd{bit}_1(1),\cd{bit}_2(0),\cd{bit}_3(1),
			  \cd{bit}_4(1) \} )$
\end{tabbing}
\caption{Reducing DNF to a recursive program}
\label{force2 hard fig}
%\hrule
\end{figure}

An example of the construction is shown in Figure~\ref{force2 hard
fig}; we suggest that the reader refer to this figure at this point.
The basic idea behind the construction is that first, the clause $C_B$
will succeed only if the variable $Y$ is bound to $i$ and the $i$-th
term of $\phi$ succeeds (the definitions of \cd{true$_i$} and
\cd{false$_i$} are designed to ensure that this property holds);
second, the recursive clause $C_R$ is constructed so that the program
$\fcon(\phi)$ succeeds iff $C_B$ succeeds with $Y$ bound to one of the
values $1,\ldots,n$.

We will now argue more rigorously for the correctness of the
construction.  Clearly, $\finst(\eta)$ and $\fcon(\phi)$ are of the
same size as $\eta$ and $\phi$ respectively. Since $\db_{n,r}$ is also
of polynomial size, this reduction is polynomial.

\begin{figure}
\centerline{\input{hacked-lintree}}
\caption{Space of proofs possible with the program $\fcon(\phi)$}
\label{lintree fig}
\end{figure}

Figure~\ref{lintree fig} shows the possible proofs that can be
constructed with the program $\fcon(\phi)$; notice that the program
$\fcon(\phi)$ succeeds exactly when the clause $C_B$ succeeds for some
value of $Y$ between 1 and $r$.  Now, if $\phi$ is true then some term
$T_i=\bigwedge_{j=1}^{s_i} l_{ij}$ must be true; in this case
$\bigwedge_{j=1}^{s_i} B_{ij}$ succeeds with
\cd{Y} bound to the value $i$ and $\bigwedge_{j=1}^{s_{i'}} B_{i'j}$
for every $i'\not=i$ also succeeds with \cd{Y} bound to $i$.  On the
other hand, if $\phi$ is false for an assignment, then each $T_i$
fails, and hence for every possible binding of $Y$ generated by
repeated use of the recursive clause $C_R$ the base clause $C_B$ will
also fail.  Thus concept membership is preserved by the mapping.

This concludes the proof.
\end{proof}

\subsection{Two Linear Recursive Clauses}
\label{two linear sec}

Recall again that a single linear closed recursive clause is
identifiable from equivalence queries \cite{CohenJAIREff}.  A
construction similar to that used in Theorem~\ref{force2 neg res} can
be used to show that this result cannot be extended to programs with
two linear recursive clauses.

\begin{theorem}  \label{dnf to ilp}
Let $\progtwodepth{d}'$ be the set of 2-clause programs consisting of
two clauses in $\lrdepth{d}$. (Thus we assume that the base case of
the recursion is given as background knowledge.)  Then for any
constants $n$ and $r$ there exists a database $\db_{n,r}\in\dbj{2}$
and a declaration $\dec_{n,r}\in\decsetj{2}$, both of sizes polynomial
in $n$, such that
\[ \dnf[n,r]\reduces\progtwodepth{1}'[\db_{n,r},\dec_{n,r}]
\]
Hence for any constants $a\geq{}2$ and $d\geq{}1$ the language family
\[ \progtwodepth{d}'[\dbset,\detdecj{a}]
\]
is uniformly polynomially predictable only if DNF is polynomially
predictable.
\end{theorem}

\begin{proof} As before, the proof makes use of a prediction-preserving
reducibility from DNF to $\progtwodepth{d}'[\db,\dec]$ for a specific
$\db$ and $\dec$.  Let us assume that $\phi$ is a DNF with $r$ terms,
and further assume that $r=2^k$. (Again, this assumption is made
without loss of generality, since the number of terms in $\phi$ can be
increased by padding with vacuous terms.)  Now consider a complete
binary tree of depth $k+1$.  The $k$-th level of this tree has exactly
$r$ nodes; let us label these nodes 1, \ldots, $r$, and give the other
nodes arbitrary labels.  Now construct a database $\db_{n,r}$ as in
Theorem~\ref{force2 neg res}, except for the following changes:
\begin{itemize}
\item The predicates \cd{true$_i$(b,y)} and \cd{false$_i$(b,y)} also
succeed when $y$ is the label of a node at some level below $k$.
\item Rather than the predicate \cd{succ}, the database contains
two predicates \cd{leftson} and \cd{rightson} that encode the
relationship between nodes in the binary tree.
\item The database includes the facts
$p(\omega_1)$, \ldots, $p(\omega_{2r})$, 
where $\omega_1$, \ldots, $\omega_{2r}$ are the leaves of the
binary tree.  These will be used as the base cases of the recursive
program that is to be learned.
\end{itemize}
Let $\rho$ be the label of the root of the binary tree.
We define the instance mapping to be
\[ \finst(b_1\ldots{}b_1) \equiv
    (p(\rho),\{\cd{bit}_1(b_1),\ldots,\cd{bit}_n(b_n) \})
\]
Note that except for the use of $\rho$ rather than 1, this is
identical to the instance mapping used in Theorem~\ref{force2 neg
res}.  Also let $\dec_{n,r}=(p,1,R)$ where $R$ contains the modes
$\cd{bit}_i(-)$, for $i=1,\ldots,n$; $\cd{true}_j(+,+)$ and
$\cd{false}_j(+,+)$, for $j=1,\ldots,r$; $\cd{leftson}(+,-)$; and
$\cd{rightson}(+,-)$.

The concept mapping $\fcon(\phi)$ is the pair of clauses
$R_1,R_2$, where $R_1$ is the clause
\[  
p(Y) \hcif \bigwedge_{k=1}^n \cd{bit}_k(X_k)
		      ~\wedge~ \bigwedge_{i=1}^r \bigwedge_{j=1}^{s_i}
					B_{ij}
		      ~\wedge~ \cd{leftson}(Y,Z)\wedge{}p(Z)
\]
and $R_2$ is the clause
\[  
p(Y) \hcif \bigwedge_{k=1}^n \cd{bit}_k(X_k)
		      ~\wedge~ \bigwedge_{i=1}^r \bigwedge_{j=1}^{s_i}
					B_{ij}
		      ~\wedge~ \cd{rightson}(Y,Z)\wedge{}p(Z)
\]
Note that both of these clause are linear recursive, determinate, and
have depth 1.  Also, the construction is clearly polynomial.
It remains to show that membership is preserved.

\begin{figure}[t]
\centerline{\input{hacked-bintree}}
\caption{Proofs possible with the program $\fcon(\phi)$}
\label{bintree fig}
\end{figure}

Figure~\ref{bintree fig} shows the space of proofs that can be
constructed with the program $\fcon(\phi)$; as in Figure~\ref{lintree
fig}, $B(i)$ abbreviates the conjunction $\bigwedge \cd{bit}_i(X_i)
\wedge \bigwedge \bigwedge B_{ij}$.  Notice that the program will
succeed only if the recursive calls manage to finally recurse to one
of the base cases $p(\omega_1)$, \ldots, $p(\omega_{2r})$, which
correspond to the leaves of the binary tree.  Both clauses will both
succeed on the the first $k-1$ levels of the tree. However, to reach
the base cases of the recursion at the leaves of the tree, the
recursion must pass through the $k$-th level of the tree; that is, one
of the clauses above must succeed on some node $y$ of the binary tree,
where $y$ is on the $k$-th level of the tree, and hence the label of
$y$ is a number between 1 and $r$.  The program thus succeeds on
$\finst(\eta)$ precisely when there is some number $y$ between 1 and
$r$ such that the conjunction $B(i)$ succeeds, which (by the argument
given in Theorem~\ref{force2 neg res}) can happen if and only if
$\phi$ is satisfied by the assignment $\eta$.  Thus, the mappings
preserve concept membership.  This completes the proof.
\end{proof}

Notice that the programs $\fcon(\phi)$ used in this proof all have the
property that the depth of every proof is logarithmic in the size of
the instances.  This means that the hardness result holds even if one
additionally restricts the class of programs to have a logarithmic
depth bound.

\subsection{Upper Bounds on the Difficulty of Learning}

The previous sections showed that several highly restricted classes of
recursive programs are at least as hard to predict as DNF.  In this
section we will show that these restricted classes are also no harder
to predict than DNF.

We will wish to restrict the depth of a proof constructed by a target
program.  Thus, let $h(n)$ be any function; we will use
$\llang_{h(n)}$ for the set of programs in the class $\llang$ such
that all proofs of an extended instance $(f,D)$ have depth bounded by
$h(\size{D})$.

\begin{theorem}\label{ilp to dnf}
Let $\dnf[n,*]$ be the language of DNF boolean functions (with any
number of terms), and recall that $\progtwodepth{d}$ is the language
of 2-clause programs consisting of one clause in $\lrdepth{d}$ and one
clause in $\nrdepth{d}$, and that $\progtwodepth{d}'$ is the language
of 2-clause programs consisting of two clauses in $\lrdepth{d}$.

For all constants $d$ and $a$, and all databases $\db\in\dbset$ and
declarations $\dec\in\detdecj{a}$, there is a polynomial function
$\poly(n)$ such that
\begin{itemize}
\item $\progtwodepth{d}[\db,\dec]\reduces{}\dnf[\poly(\size{\db}),*]$
\item $\progtwodepth{d}_{h(n)}'[\db,\dec]\reduces{}\dnf[\poly(\size{\db}),*]$
if $h(n)$ is bounded by $c\log{}n$ for some constant $c$.
\end{itemize}
Hence if either of these language families is uniformly polynomially
predictable, then $\dnf[n,*]$ is polynomially predictable.
\end{theorem}

\begin{proof} 
The proof relies on several facts established in the companion
paper \cite{CohenJAIREff}.
\begin{itemize}
\item For every declaration $\dec$, 
there is a clause $\clongd{d}(\dec)$ such that every nonrecursive
depth-$d$ determinate clause $C$ is equivalent to some subclause of
$\clongd{d}$. Further, the size of $\clong{d}$ is polynomial in
$\dec$.  This means that the language of subclauses of $\clong$ is a
normal form for nonrecursive constant-depth determinate clauses.

\item Every linear closed recursive clause $C_R$ that is
constant-depth determinate is equivalent to some subclause of $\clong$
plus a recursive literal $L_r$; further, there are only a polynomial
number of possible recursive literals $L_r$.

\item For any constants $a$, $a'$, and $d$, any database $\db\in\dbj{a}$,
any declaration $\dec=(p,a',R)$, any database $\db\in\dbj{a}$, and any
program $P$ in $\progtwodepth{d}[\db,\dec]$, the depth of a
terminating proof constructing using $P$ is no more than $h_{\max}$,
where $h_{\max}$ is a polynomial in the size of $\db$ and $\dec$.

\item At can be assumed without loss of generality that the database
$\db$ and all decsriptions $D$ contain an \trm{equality predicate},
where an equality predicate is simply a predicate \cd{equal(X,Y)}
which is true exactly when $X=Y$.
\end{itemize}
The idea of the proof is to contruct a prediction-preserving reduction
between the two classes of recursive programs listed above to and DNF.
We will begin with two lemmas.

\begin{lemma} \label{det to mon lemma} Let $\dec\in\detdecj{a}$, and let $C$
be a nonrecursive depth-$d$ determinate clause consistent with $\dec$.
Let $\subcl_C$ denote the language of subclauses of $C$, and let
$\monomial[u]$ denote the language of monomials over $u$ variables.
Then there is a polynomial $\poly_1$ so that for any database
$\db\in\dbset$,
\[ \subcl_C[\db,\dec]\reduces\monomial[\poly_1(\size{\db})]
\]
\end{lemma}

\begin{lemmaproof} Follows immediately from the construction used in 
Theorem~1 of D\u{z}eroski, Muggleton, and Russell
\cite{DzeroskiCOLT92}.  (The basic idea of the construction is to
introduce a propositional variable representing the ``success'' of
each connected chain of literals in $C$. Any subclause of $C$ can then
be represented as a conjunction of these propositions.)
\end{lemmaproof}

This lemma can be extended as follows.

\begin{lemma} \label{det to dnf lemma}
Let $\dec\in\detdecj{a}$, and let $S=\{C_1,\ldots,C_r\}$ be a set of
$r$ nonrecursive depth-$d$ determinate clauses consistent with $\dec$,
each of length $n$ or less.  Let $\subcl_S$ denote the set of all
programs of the form $P=(D_1,\ldots,D_s)$ such that each $D_i$ is a
subclause of some $C_j\in{}S$.  

Then there is a polynomial $\poly_2$ so that for any database
$\db\in\dbset$,
\[ 
\subcl_S[\db,\dec]\reduces\dnf[\poly_2(\size{DB},r),*]
\]
\end{lemma}

\begin{lemmaproof} By Lemma~\ref{det to mon lemma}, for each $C_i\in{}S$,
there is a set of variables $V_i$ of size polynomial in $\size{\db}$
such that every clause in $\subcl_{C_i}$ can be emulated by a monomial
over $V_i$.  Let $V=\bigcup_{i=1}^r V_i$. Clearly, $|V|$ is
polynomial in $n$ and $r$, and every clause in
$\bigcup_{i}\subcl_{C_i}$ can be also emulated by a monomial over $V$.
Further, every disjunction of $r$ such clauses can be represented by a
disjunction of such monomials.

Since the $C_i$'s all satisfy a single declaration $\dec=(p,a,R)$,
they have heads with the same principle function and arity; further,
we may assume (without loss of generality, since an equality predicate
is assumed) that the variables appearing in the heads of these clauses
are all distinct.  Since the $C_i$'s are also nonrecursive, every
program $P\in\subcl_S$ can be represented as a disjunction
\( D_1\vee\ldots\vee{}D_r
\) where for all $i$, $D_i\in(\bigcup_i\subcl_{C_i})$.  Hence every
$P\in\subcl_S$ can be represented by an $r$-term DNF over the set of
variables $V$.
\end{lemmaproof}

Let us now introduce some additional notation.  If $C$ and $D$ are
clauses, then we will use $C\resolves{}D$ to denote the result of
resolving $C$ and $D$ together, and $C^i$ to denote the result of
resolving $C$ with itself $i$ times.  Note that $C\resolves{}D$ is
unique if $C$ is linear recursive and $C$ and $D$ have the same
predicate in their heads (since there will be only one pair of
complementary literals.)

\begin{sloppypar}
Now, consider some target program 
\[ P=(C_R,C_B)\in\progtwodepth{d}[\db,\dec]
\]
where $C_R$ is the recursive clause and $C_B$ is the base.  The proof of any
extended instance $(f,D)$ must use clause $C_R$ repeatedly $h$ times 
and then use clause $C_B$ to resolve away the final subgoal.
Hence the nonrecursive clause $C_R^h\resolves{}C_B$ could also be used to
cover the instance $(f,D)$.

Since the depth of any proof for this class of programs is bounded by
a number $h_{\it max}$ that is polynomial in $\size{DB}$ and $\maxi$,
the nonrecursive program
\[ P' = \{ C_R^h\resolves{}C_B : 0\leq{}h\leq{}h_{\it max} \}
\] 
is equivalent to $P$ on extended instances of size $\maxi$ or less.

Finally, recall that we can assume that $C_B$ is a subclause of
$\clongd{d}$; also, there is a polynomial-sized set
\( L_{\cal R} = L_{r_1},\ldots,L_{r_p} 
\) 
of closed recursive literals such that for some $L_{r_i}\in{}L_{\cal
R}$, the clause $C_R$ is a subclause of $\clongd{d}\cup{}L_{r_i}$.
This means that if we let $S$ be the polynomial-sized set
\[ S_1 = \{ (\clongd{d}\cup{}L_{r_i})^h\resolves{}\clongd{d} ~~|~~
	0\leq{}h\leq{}h_{\it max} 
	\mbox{~and~}
	 L_{r_i}\in{}L_{\cal R} \}
\] 
then $P'\in{}\subcl_{S_1}$.  Thus by Lemma~\ref{det to dnf lemma},
$\progtwodepth{d}\reduces{}\dnf$.
This concludes the proof of the first statement in the the
theorem.  

To show that 
\[ \progtwodepth{d}_{h(n)}'[\db,\dec]\reduces{}\dnf[\poly(\size{\db},*]
\]
a similar argument applies.  Let us again introduce some
notation, and define 
$\mesh{h}{n}{C_{R_1}}{C_{R_2}}$ as the set of all
clauses of the form
\[ C_{R_{i,1}}\resolves{}C_{R_{i,2}}\resolves{}\ldots
	\resolves{}C_{R_{i,h'}}
\] 
where for all $j$, $C_{R_{ij}}=C_{R_1}$ or $C_{R_{ij}}=C_{R_2}$, and
$h'\leq{}h(n)$.  Notice that for functions $h(n)\leq{}c\log{}n$ the
number of such clauses is polynomial in $n$.

Now let $p$ be the predicate appearing in the heads of $C_{R1}$ and
$C_{R_2}$, and let $\hat{C}$ (respectively $\hat{\db}$) be a a version
of $C$ ($\db$) in which every instance of the predicate $p$ has been
replaced with a new predicate $\hat{p}$.  If $P$ is a recursive
program $P=\{C_{R_1},C_{R_2}\}$ in $\progtwodepth{d}'$ over the
database $\db$, then $P\wedge\db$ is equivalent\footnote{On extended
instances of size $\maxi$ or less.} to the nonrecursive program
$P'\wedge\hat{DB}$, where
\[ P' = \{ \hat{C} ~|~ C\in\mesh{h}{\maxi}{C_{R_1}}{C_{R_2}} \}
\] 
\end{sloppypar}

Now recall that there are a polynomial number of recursive literals
$L_{r_i}$, and hence a polynomial number of pairs of recursive literals
$L_{r_i},L_{r_j}$.  This means that the set of clauses
\[ S_2 = \bigcup_{(L_{r_i},L_{r_j})\in{}L_{\cal R}\times{}L_{\cal R}}
  \{ \hat{C} ~|~
    C\in\mesh{h}{\maxi}{\clongd{d}\cup{}L_{r_i}}{\clongd{d}\cup{}L_{r_j}} \} 
\]
is also polynomial-sized; furthermore, for any program $P$ in the
language $\progtwodepth{d}$, $P'\in\subcl_{S_2}$.  The second part of
the theorem now follows by application of Lemma~\ref{det to dnf
lemma}.
\end{proof}

\begin{sloppypar}
An immediate corollary of this result is that Theorems~\ref{dnf to
ilp} and \ref{force2 neg res} can be strengthened as follows.
\end{sloppypar}

\begin{corollary}
For all constants $d\geq{}1$ and $a\geq{}2$, 
the language family 
\[ \progtwodepth{d}[\dbset,\detdecj{a}]
\]
is uniformly polynomially predictable if and only if DNF is
polynomially predictable.

For all constants $d\geq{}1$ and $a\geq{}2$, 
the language family 
\[ \progtwodepth{d}'[\dbset,\detdecj{a}]
\]
is uniformly polynomially predictable if and only if DNF is
polynomially predictable.
\end{corollary}

Thus in an important sense these learning problems are equivalent to
learning boolean DNF.  This does not resolve the questions of the
learnability of these languages, but does show that their
learnability is a difficult formal problem: the predictability of
boolean DNF is a long-standing open problem in computational learning
theory.

\section{Related Work} 
\label{related work sec}

The work described in this paper differs from previous formal work on
learning logic programs in simultaneously allowing background
knowledge, function-free programs, and recursion.  We have also
focused exclusively on computational limitations on efficient
learnability that are associated with recursion, as we have considered
only languages known to be pac-learnable in the nonrecursive case.
Since the results of this paper are all negative, we have concentrated
on the model of polynomial predictability; negative results in this
model immediately imply a negative result in the stronger model of
pac-learnability, and also imply negative results for all strictly
more expressive languages.

Among the most closely related prior results are the negative results
we have previously obtained for certain classes of nonrecursive
function-free logic programs \cite{CohenNonRecJnl93}. These results
are similar in character to the results described here, but apply to
nonrecursive languages.  Similar cryptographic results have been
obtained by Frazier and Page \citeyear{FrazierILP93} for certain
classes of programs (both recursive and nonrecursive) that contain
function symbols but disallow background knowledge.

Some prior negative results have also been obtained on the
learnability of other first-order languages using the proof technique
of \trm{consistency hardness} \cite{PittJACM88}.  Haussler
\citeyear{HausslerMLJ89} showed that the language of ``existential
conjunction concepts'' is not pac-learnable by showing that it can be
hard to find a concept in the language consistent with a given set of
examples.  Similar results have also been obtained for two restricted
languages of Horn clauses \cite{KietzECML93}; a simple description
logic \cite{CohenMLJDL}; and for the language of sorted first-order
terms \cite{PageILP92}.  All of these results, however, are specific
to the model pac-learnability, and none can be easily extended to the
polynomial predictability model considered here.  The results also do
not extend to languages more expressive than these specific
constrained languages.  Finally, none of these languages allow
recursion.

To our knowledge, there are no other negative learnability results for
first-order languages. A discussion of prior positive learnability
results for first-order languages can be found in the companion paper
\cite{CohenJAIREff}.

\section{Summary}
\label{summary sec}

This paper and its companion \cite{CohenJAIREff} have considered a
large number of different subsets of Datalog.  Our aim has been to be
not comprehensive, but systematic: in particular, we wished to find
precisely where the boundaries of learnability lie as various
syntactic restrictions are imposed and relaxed.  Since it is all too
easy for a reader to ``miss the forest for the trees'', we will now
briefly summarize the results contained in this paper, together with
the positive results of the companion paper
\cite{CohenJAIREff}.

Throughout these papers, we have assumed that a polynomial amount of
background knowledge exists; that the programs being learned contain
no function symbols; and that literals in the body of a clause have
small arity.  We have also assumed that recursion is \trm{closed},
meaning that no output variables appear in a recursive clause;
however, we believe that this restriction can be relaxed without
fundamentally changing the results of the paper.

\newcommand{\new}[1]{\fbox{$#1$}}
\newcommand{\old}[1]{($#1$)}
\newcommand{\cor}[1]{$#1$}
\newcommand{\hard}[1]{#1^-}
\newcommand{\easy}[1]{#1^+}
\newcommand{\ednf}[1]{#1^{={\rm DNF}}}
\newcommand{\gdnf}[1]{#1^{\geq{\rm DNF}}}

\begin{table}
\begin{center}
\begin{tabular}{|c|cc|ccc|}
\hline
Local & \multicolumn{5}{c|}{Constant-Depth Determinate} \\
Clauses & \multicolumn{5}{c|}{Clauses} \\
\hline
\hline
& & \multicolumn{1}{c}{} & & & \\
\cor{\hard{nC_R}}       & \new{\hard{nC_R}}      & \multicolumn{1}{c}{\cor{\hard{nC_R|C_B}}}
& \cor{\hard{nC_R,C_B}} & \cor{\hard{k\times{}nC_R}} & \cor{\hard{n\times{}nC_R}}
\\ & & \multicolumn{1}{c}{} & & & \\
\cline{2-3} 
& & & & & \\
\cor{\hard{kC_R}}       & \new{\easy{kC_R}}      & \cor{\easy{kC_R|C_B}} 
& \cor{\gdnf{kC_R,C_B}} & \cor{\gdnf{k\times{}k'C_R}} & \cor{\hard{n\times{}kC_R}}
\\  & & & & & \\
 & & & & & \\
\new{\hard{1C_R}}       & \new{\easy{1C_R}}         & \new{\easy{1C_R|C_B}} 
& \new{\ednf{1C_R,C_B}} & \new{\ednf{2\times{}1C_R}} & \new{\hard{n\times{}1C_R}}
\\  & & & & & \\
%\old{\easy{C_B}}        & \old{\easy{C_B}}       & 		      
%&                       &                        &   \\
%& & & & & \\
\hline
\end{tabular}
\end{center}
\caption{A summary of the learnability results}
\label{summ tab}
\end{table}


In the companion paper \cite{CohenJAIREff} we showed that a single
nonrecursive constant-depth determinate clause was learnable in the
strong model of
\trm{identification from equivalence queries}.  In this learning
model, one is given access to an oracle for counterexamples---that is,
an oracle that will find, in unit time, an example on which the
current hypothesis is incorrect---and must reconstruct the target
program exactly from a polynomial number of these counterexamples.
This result implies that a single nonrecursive constant-depth
determinate clause is pac-learnable (as the counterexample oracle can
be emulated by drawing random examples in the pac setting).  The
result is not novel \cite{DzeroskiCOLT92}; however the proof given is
independent, and is also of independent interest.  Notably, it is
somewhat more rigorous than earlier proofs, and also proves the result
directly, rather than via reduction to a propositional learning
problem.  The proof also introduces a simple version of the
\trm{forced simulation} technique, variants of which are used in all
of the positive results.

We then showed that the learning algorithm for nonrecursive clauses
can be extended to the case of a single \trm{linear recursive}
constant-depth determinate clause, leading to the result that this
restricted class of recursive programs is also identifiable from
equivalence queries.  With a bit more effort, this algorithm can be
further extended to learn a single $k$-ary recursive constant-depth
determinate clause.

We also considered extended the learning algorithm to learn recursive
\trm{programs} consisting of more than one constant-depth determinate
clauses.  The most interesting extension was to simultaneously learn a
recursive clause $C_R$ and a base clause $C_B$, using equivalence
queries and also a ``basecase oracle'' that indicates which
counterexamples should be covered by the base clause $C_B$.  In this
model, it is possible to simultaneously learn a recursive clause and a
nonrecursive base case in all of the situations for which a recursive
clause is learned alone; for instance, one can learn a $k$-ary
recursive clause to together with its nonrecursive base case.  This
was our strongest positive result.

\begin{table}
\begin{small}
\begin{center}
\begin{tabular}{|lllllll|}
\hline
Language Family & B & R & L/R 	&  Oracles 	&  Notation & Learnable \\
\hline
$\nrdepth{d}[\dbj{a},\detdecj{a}]$    & 1 & 0 & $-$ & EQ   	& $C_B$		& yes \\
$\lrdepth{d}[\dbj{a},\detdecj{a}]$    & 0 & 1 & 1   & EQ   	& $1C_R$	& yes \\
$\krdepth{d}{k}[\dbj{a},\detdecj{a}]$ & 0 & 1 & $k$ & EQ   	& $kC_R$	& yes \\
$\progtwodepth{d}[\dbj{a},\detdecj{a}]$& 1 & 1 & 1   & EQ,BASE 	& $1C_R|C_B$	& yes \\
$\maxlang[\dbj{a},\detdecj{a}]$	      & 1 & 1 & $k$ & EQ,BASE 	& $kC_R|C_B$	&yes \\
$\progtwodepth{d}[\dbj{a},\detdecj{a}]$& 1 & 1 & 1   & EQ   	& $1C_R,C_B$	&$=$DNF \\
$\progtwodepth{d}'[\dbj{a},\detdecj{a}]$&0 & 2 & 1   & EQ   	& $2\times{}1C_R$ &$=$DNF \\
$\lrdepthprog{d}[\dbj{a},\detdecj{a}]$& 0 & $n$ & 1 & EQ   	& $n\times{}1C_R$ &no \\
$\rdepth{d}[\dbj{a},\detdecj{a}]$     & 0 & 1   & $n$ & EQ 	& $nC_R$	&no	\\
%&  &  &  &   & \\
$\lrlocal{k}[\dbj{a},\decj{a}]$       & 0 & 1 & 1   & EQ   	& $1C_R$	&no \\
\hline
\end{tabular}
\end{center}
\end{small}

\caption{Summary by language of the learnability results.
Column B indicates the number of base (nonrecursive) clauses allowed
in a program; column R indicates the number of recursive clauses; L/R
indicates the number of recursive literals allowed in a single
recursive clause; EQ indicates an oracle for equivalence queries and
BASE indicates a basecase oracle.  For all languages except
$\lrlocal{k}$, all clauses must be determinate and of depth $d$.}
\label{summ tab 2}
\end{table}

These results are summarized in Tables~\ref{summ tab} and \ref{summ
tab 2}.  In Table~\ref{summ tab}, a program with one $r$-ary recursive
clause is denoted $rC_R$, a program with one $r$-ary recursive clause
and one nonrecursive basecase is denoted $rC_R,C_B$, or $rC_R|C_B$ if
there is a ``basecase'' oracle, and a program with $s$ different
$r$-ary recursive clauses is denoted $s\times{}rC_R$. The boxed
results are associated with one or more theorems from this paper, or
its companion paper, and the unmarked results are corollaries of other
results.  A ``$+$'' after a program class indicates that it is
identifiable from equivalence queries; thus the positive results
described above are summarized by the four ``$+$'' entries in the
lower left-hand corner of the section of the table concerned with
constant-depth determinate clauses.

Table~\ref{summ tab 2} presents the same information in a slightly
different format, and also relates the notation of Table~\ref{summ
tab} to the terminology used elsewhere in the paper.

This paper has considered the learnability of the various natural
generalizations of the languages shown to be learnable in the
companion paper.  Consider for the moment single clauses.  The
companion paper showed that for any fixed $k$ a single $k$-ary
recursive constant-depth determinate clause is learnable.  Here we
showed that all of these restrictions are necessary.  In particular, a
program of $n$ constant-depth linear recursive clauses is not
polynomially predictable; hence the restriction to a single clause is
necessary. Also, a {single\/} clause with $n$ recursive calls is hard
to learn; hence the restriction to $k$-ary recursion is necessary.  We
also showed that the restriction to constant-depth determinate clauses
is necessary, by considering the learnability of \trm{constant
locality clauses}.  Constant locality clauses are the only known
generalization of constant-depth determinate clauses that are
pac-learnable in the nonrecursive case.  However, we showed that if
recursion is allowed, then this language is {\em not\/} learnable:
even a single linear recursive clause is not polynomially predictable.

Again, these results are summarized in Table~\ref{summ tab}; a ``$-$''
after a program class means that it is not polynomially predictable,
under cryptographic assumptions, and hence neither pac-learnable nor
identifiable from equivalence queries.

The negative results based on cryptographic hardness give an upper
bound on the expressiveness of learnable recursive languages, but
still leave open the learnability of programs with a constant number
of $k$-ary recursive clauses in the absence of a basecase oracle.  In
the final section of this paper, we showed that the following problems
are, in the model of polynomial predictability, equivalent to
predicting boolean DNF:
\begin{itemize}
\item predicting two-clause constant-depth determinate
recursive programs containing
one linear recursive clause and one base case;
\item predicting two-clause recursive constant-depth determinate
programs containing two linear recursive clauses, even if the base
case is known.
\end{itemize} 
We note that these program classes are the very nearly the simplest
classes of multi-clause recursive programs that one can imagine, and
that the pac-learnability of DNF is a long-standing open problem in
computational learning theory.  These results suggest, therefore, that
pac-learning multi-clause recursive logic programs is difficult; at
the very least, they show that finding a provably correct pac-learning
algorithm will require substantial advances in computational learning
theory.  In Table~\ref{summ tab}, a ``$=\dnf$'' (respectively
$\geq{}\dnf$) means that the corresponding language is
prediction-equivalent to DNF (respectively at least as hard as DNF).

To further summarize Table~\ref{summ tab}: with any sort of recursion,
only programs containing constant-depth determinate clauses are
learnable.  The only constant-depth determinate recursive programs
that are learnable are those that contain a single $k$-ary recursive
clause (in the standard equivalence query model) or a single $k$-ary
recursive clause plus a base case (if a ``basecase oracle'' is
allowed).  All other classes recursive programs are either
cryptographically hard, or as hard as boolean DNF.

\section{Conclusions}

Inductive logic programming is an active area of research, and one
broad class of learning problems considered in this area is the class
of ``automatic logic programming'' problems. Prototypical examples of
this genre of problems are learning to append two lists, or to
multiply two numbers.  Most target concepts in automatic logic
programming are recursive programs, and often, the training data for
the learning system are simply examples of the target concept,
together with suitable background knowledge.

The topic of this paper is the pac-learnability of recursive logic
programs from random examples and background knowledge; specifically,
we wished to establish the computational limitations inherit in
performing this task.  We began with some positive results established
in a companion paper. These results show that one constant-depth
determinate closed $k$-ary recursive clause is pac-learnable, and that
further, a program consisting of one such recursive clause and one
constant-depth determinate nonrecursive clause is also pac-learnable
given an additional ``basecase oracle''.

In this paper we showed that these positive results are not likely to
be improved. In particular, we showed that either eliminating the
basecase oracle or learning two recursive clauses simultaneously is
prediction-equivalent to learning DNF, even in the case of linear
recursion.  We also showed that the following problems are as hard as
breaking (presumably) secure cryptographic codes: pac-learning $n$
linear recursive determinate clauses, pac-learning one $n$-ary
recursive determinate clause, or pac-learning one linear recursive
$k$-local clause.

These results contribute to machine learning in several ways.  From
the point of view of computational learning theory, several results
are technically interesting.  One is the prediction-equivalence of
several classes of restricted logic programs and boolean DNF; this
result, together with others like it \cite{CohenNonRecJnl93},
reinforces the importance of the learnability problem for DNF.  This
paper also gives a dramatic example of how adding recursion can have
widely differing effects on learnability: while constant-depth
determinate clauses remain pac-learnable when linear recursion is
added, constant-locality clauses become cryptographically hard.

Our negative results show that systems which apparently learn a larger
class of recursive programs must be taking advantage either of some
special properties of the target concepts they learn, or of the
distribution of examples that they are provided with.  We believe that
the most likely opportunity for obtaining further positive formal
results in this area is to identify and analyze these special
properties.  For example, in many examples in which FOIL has learned
recursive logic programs, it has made use of ``complete example
sets''---datasets containing all examples of or below a certain size,
rather than sets of randomly selected examples
\cite{QuinlanECML93}.  It is possible that complete datasets allow a more
expressive class of programs to be learned than random datasets; in
fact, some progress has been recently made toward formalizing this
conjecture \cite{DeRaedtILP94}.

Finally, and most importantly, this paper has established the
boundaries of learnability for determinate recursive programs in the
pac-learnability model.  In many plausible automatic programming
contexts it would be highly desirable to have a system that offered
some formal guarantees of correctness.  The results of this paper
provide upper bounds on what one can hope to achieve with an
efficient, formally justified system that learns recursive programs
>from random examples alone.

\vskip 0.2in

\acks{The author wishes to thank three anonymous JAIR reviewers
for a number of useful suggestions on the presentation and technical
content.}

\bibliography{/home/wcohen/papers/bib/cohen,/home/wcohen/papers/bib/ml,/home/wcohen/papers/bib/se,/home/wcohen/papers/bib/books,/home/wcohen/papers/bib/colt,/home/wcohen/papers/bib/misc}
\bibliographystyle{theapa}


\newpage

\end{document}



