This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are efficiently learnable from examples. More precisely, this result is established for k-DL the set of decision lists with conjunctive clauses of size k at each decision. Since k-DL properly includes other well-known techniques for representing Boolean functions such as k-CNF (formulae in conjunctive normal form with at most k literals per clause), k-DNF (formulae in disjunctive normal form with at most k literals per term), and decision trees of depth k, our result strictly increases the set of functions that are known to be polynomially learnable, in the sense of Valiant (1984). Our proof is constructive: we present an algorithm that can efficiently construct an element of k-DL consistent with a given set of examples, if one exists.

We call A the database or base set of beliefs of the system. Consider, for example, the following sentence about birds: "All In this chapter, we explore three methods. These methods have several potential applications. We define the effects of the CWA in terms of customary logical notation. We call our belief set, A, the proper axioms of a theory. T[A] by adding a set, Aasm, of assumed beliefs. CWA adds'IQ (B), since A does not logically entail U(B). The CWA often is used with database systems. The following example shows that it does not. Let A contain only the clause P(A) V P(B) . THEOREM 6.1 CWA[A] is consistent if and only if, for every positive-- Proof CWA[A] can be inconsistent only if A U A,"m is.

We address the problem of designing programming systems to reason with and about constraints. Taking a logic programming approach, we define a class of programming languages, the CLP languages, all of which share the same essential semantic properties. From a conceptual point of view, CLP programs are highly declarative and are soundly based within a unified framework of formal semantics. This framework not only subsumes that of logic programming, but satisfies the core properties of logic programs more naturally. From a user's point of view, CLP programs have great expressive power due to the constraints which they naturally manipulate.

This report describes recent and continuing research in artificial intelligence and related fields being conducted at the University of Pennsylvania. Although AI research takes place primarily in the Department of Computer and Information Science ( in School of Engineering and Applied Science), many aspects of this research are preformed in collaboration with other engineering departments as well as other schools at the University, such as the College of Arts and Sciences, the School of Medicine, and Wharton School.

One to organize the construction teams. One to hack the planning system. How many AI people does it take to change a lightbulb? One to get Westinghouse to sponsor the research. One to indicate about how the robot mimics human motor A. At least 55: The knowledge engineering group (6): One to define the goal state.

Twenty-five years ago I had a dream, a daydream, if you will. A dream shared with many of you. I dreamed of a special kind of computer, which had eyes and ears and arms and legs, in addition to its "brain." I did not dream that this new computer friend would be a means of making money for me or my employer or a help for my country - though I loved my country then and still do, and I have no objection to making money. I did not even dream of such a worthy cause as helping the poor and handicapped of the world using this marvelous new machine. No, my dream was filled with the wild excitement of seeing a machine act like a human being, at least in many ways.

We present a new technique for obtaining decision procedures for modal logics of programs. The technique centers around a new class of finite automata on infinite trees for which the emptiness problem can be solved in polynomial time. The decision procedures then consist of constructing an automaton Af for a given formula f such that Af accepts some tree if and only if f is satisfiable. We illustrate our technique by giving exponential decision procedures for several variants of deterministic propositional dynamic logic.

Raymond Reiter' Department of Computer Science University of Toronto Toronto, Ontario, Canada M5S-1A4 Johan de Kleer Intelligent Systems Laboratory XEROX Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, California 94304 ABSTRACT In this paper we (1) define the concept of a Clause Managetnent System (CMS) A Problem-Solving Architecture Figure 1 illustrates an architecture for a problem solving system consisting of a domain dependent Reasoner coupled to a domain independent Clause Management System (CMS). For our present purposes, the Reasoner is a black box which, m the process of doing whatever it does, occasionally transmits a propositional clause 2 to the CMS.

While program verification was always a. desirable, but never an easy task, the advent of concurrent

Formal proof-checking has long been recognized as an interesting application of computers. It has often been claimed that significant proofs in mathematics cannot be checked using an automatic proof-checker, and that formal proofs lack the intuitive plausibility and insight that informal proofs possess. We argue against these claims by presenting machine-checked versions of some landmark proofs in metamathematics, such as those of the tautology theorem, Godel's incompleteness theorem, and the Church-Rosser theorem. These proofs were checked using the Boyer-Moore theorem power. The tautology theorem and the incompleteness theorem are proved by first defining a proof-checker for the formal theory Z2 in the Boyer-Moore logic.