Inductive theorem provers often diverge. This paper describes a simple critic, a computer program which monitors the construction of inductive proofs attempting to identify diverging proof attempts. Divergence is recognized by means of a ``difference matching'' procedure. The critic then proposes lemmas and generalizations which ``ripple'' these differences away so that the proof can go through without divergence. The critic enables the theorem prover Spike to prove many theorems completely automatically from the definitions alone.

Termination of logic programs with negated body atoms (here called general logic programs) is an important topic. One reason is that many computational mechanisms used to process negated atoms, like Clark's negation as failure and Chan's constructive negation, are based on termination conditions. This paper introduces a methodology for proving termination of general logic programs w.r.t. the Prolog selection rule. The idea is to distinguish parts of the program depending on whether or not their termination depends on the selection rule. To this end, the notions of low-, weakly up-, and up-acceptable program are introduced. We use these notions to develop a methodology for proving termination of general logic programs, and show how interesting problems in non-monotonic reasoning can be formalized and implemented by means of terminating general logic programs.

(Bledsoe 1976). We didn't know we were being We spent a lot of time reading by ourselves, because most of the time the other grades were having their classes. But we DID learn, and had some pretty died on 4 October 1995 of ALS, good teachers (Bledsoe 1976). Woody was one of the and recalls spending "hours just roaming founders of AI, making early contributions in around, sometimes working mathematics pattern recognition and automated reasoning. He continued to make significant contributions When Woody was 12, his father died. It was to AI throughout his long career. His a devastating blow both emotionally and legacy consists not only of his scientific work financially. As Woody recalled, "We were poor but also of several generations of scientists before, but after papa died in January 1934, who learned from Woody the joy of scientific things got worse" (Bledsoe 1976). He and the research and the way to go about it. Woody's rest of his brothers and sisters worked dreary enthusiasm, his perpetual sense of optimism, 10-hour days to make ends meet. He to humanity offered those who knew him the found work in north Texas driving a tractor all hope and comfort that truly good and great night. After a month, he hopped a freight men do exist. He graduated little farm near Maysville, Oklahoma. He moved to Oklahoma to try his took a job as a dishwasher, working 12-hour luck at farming. Woody was the fourth child days 7 days a week. In for his heroic activities in arranging the April, the restaurant owner forced him back transportation of troops across the Rhine into working 12-hour days, which was too in March, 1945. He left the Rhine bridges except the one at Remagen university without saying goodbye and had been destroyed by the retreating German joined the United States Army. Patton's Third Army decided to cross the Rhine by boats near Frankfurt rather than suffer the delay of waiting for bridge construction. Therefore the went to Officer's Candidate School (OCS) Army Corps of Engineers hauled naval By the time he in 1942, he had been promoted to second landing craft (designed for beach landings) lieutenant. While at OCS, Woody had an by truck across Europe to ferry experience that had a profound effect on him: troops across the Rhine. Bledsoe, by then an Army captain, recalls that there was Another experience at OCS at Fort only light enemy fire during the crossing; Belvoir left a lasting impression on me. His first "research" was experimenting army truck. The simple idea opened the flap and said, "Get out here. of backing the trucks into the water, Let's do the map reading." He would later father a to get on with the work, to finish the son, Greg, born in March 1947. It taught me that "if we have to had two more children, Pam and Lance.

The paper describes an extension of well-founded semantics for logic programs with two types of negation. In this extension information about preferences between rules can be expressed in the logical language and derived dynamically. This is achieved by using a reserved predicate symbol and a naming technique. Conflicts among rules are resolved whenever possible on the basis of derived preference information. The well-founded conclusions of prioritized logic programs can be computed in polynomial time. A legal reasoning example illustrates the usefulness of the approach.

Learning and reasoning are both aspects of what is considered to be intelligence. Their studies within AI have been separated historically, learning being the topic of machine learning and neural networks, and reasoning falling under classical (or symbolic) AI. However, learning and reasoning are in many ways interdependent. This paper discusses the nature of some of these interdependencies and proposes a general framework called FLARE, that combines inductive learning using prior knowledge together with reasoning in a propositional setting. Several examples that test the framework are presented, including classical induction, many important reasoning protocols and two simple expert systems.

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.

We present algorithms that learn certain classes of function-free recursive logic programs in polynomial time from equivalence queries. In particular, we show that a single k-ary recursive constant-depth determinate clause is learnable. Two-clause programs consisting of one learnable recursive clause and one constant-depth determinate non-recursive clause are also learnable, if an additional ``basecase'' oracle is assumed. These results immediately imply the pac-learnability of these classes. Although these classes of learnable recursive programs are very constrained, it is shown in a companion paper that they are maximally general, in that generalizing either class in any natural way leads to a computationally difficult learning problem. Thus, taken together with its companion paper, this paper establishes a boundary of efficient learnability for recursive logic programs.

The most commonly used neural network models are not well suited to direct digital implementations because each node needs to perform a large number of operations between floating point values. Fortunately, the ability to learn from examples and to generalize is not restricted to networks ofthis type. Indeed, networks where each node implements a simple Boolean function (Boolean networks) can be designed in such a way as to exhibit similar properties. Two algorithms that generate Boolean networks from examples are presented. The results show that these algorithms generalize very well in a class of problems that accept compact Boolean network descriptions. The techniques described are general and can be applied to tasks that are not known to have that characteristic. Two examples of applications are presented: image reconstruction and handwritten character recognition.

The most commonly used neural network models are not well suited to direct digital implementations because each node needs to perform a large number of operations between floating point values. Fortunately, the ability to learn from examples and to generalize is not restricted to networks ofthis type. Indeed, networks where each node implements a simple Boolean function (Boolean networks) can be designed in such a way as to exhibit similar properties. Two algorithms that generate Boolean networks from examples are presented. The results show that these algorithms generalize very well in a class of problems that accept compact Boolean network descriptions. The techniques described are general and can be applied to tasks that are not known to have that characteristic. Two examples of applications are presented: image reconstruction and handwritten character recognition.

The most commonly used neural network models are not well suited to direct digital implementations because each node needs to perform alarge number of operations between floating point values. Fortunately, the ability to learn from examples and to generalize is not restricted to networks ofthis type. Indeed, networks where each node implements a simple Boolean function (Boolean networks) can be designed in such a way as to exhibit similar properties. Two algorithms that generate Boolean networks from examples are presented. Theresults show that these algorithms generalize very well in a class of problems that accept compact Boolean network descriptions.