By placing various restrictions on the heuristic estimator it is possible to constrain the heuristic search process to fit specific needs. This paper introduces a new restriction upon the heuristic, called the “bandwidth” condition, that enables the ordered search to better cope with time and space difficulties. In particular, the effect of error within the heuristic is considered in detail. Beyond this, the bandwidth condition quite naturally allows for the extension of the heuristic search to MIN/MAX trees. The resulting game playing algorithm affords many desirable practical features not found in minimax based techniques, as well as maintaining the theoretical framework of ordered searches.

"The epistemological part of Al studies what kinds of facts about the world are available to an observer with given opportunities to observe, how these facts can be represented in the memory of a computer, and what rules permit legitimate conclusions to be drawn from these facts. It leaves aside the heuristic problems of how to search spaces of possibilities and how to match patterns."See also: IJCAI 5, 1038-1044In Readings in Artificial Intelligence, B.L. Webber and N.J. Nilsson (eds.), Tioga Publishing, 1981.

AI Memo 389, AI Laboratory, Massachusetts Instituteof Technology.

"An important research problem in artificial intelligence is the study of methods for learning general concepts or rules from a set of training instances. An approach to this problem is presented which is guaranteed to find, without backtracing, all rule versions consistent with a set of positive and negative training instances. The algorithm put forth uses a representation of the space of those rules consistent with the observed training data. This "rule version space" is modified in response to new training instances by eliminating candidate rule versions found to conflict with each new instance. The use of version spaces is discussed in the context of Meta-DENDRAL, a program which learns rules in the domain of chemical spectroscopy."Proc. IJCAI 77 VOL 1 MASSACHUSETTS INSTITUTE OF TECHNOLOGY CAMBRIDGE, MASSACHUSETTS, USA AUGUST 22 - 25 , 1977, pp.305-310

Sentences in first-order predicate logic can be usefully interpreted as programs. In this paper the operational and fixpoint semantics of predicate logic programs are defined, and the connections with the proof theory and model theory of logic are investigated. It is concluded that operational semantics is a part of proof theory and that fixpoint semantics is a special case of model-theoretic semantics.

In the spring of 1971, I attended a course on statistical inference taught by Arthur Dempster at Harvard. In the fall of that same year Geoffrey Watson suggested I give a talk expositing Dempster's work on upper and lower probabilities to the Department of Statistics at Princeton. This essay is one of the results of the ensuing effort. It offers a reinterpretation of Dempster's work, a reinterpretation that identifies his "lower probabilities" as epistemic probabilities or degrees of belief, takes the rule for combining such degrees of belief as fundamental, and abandons the idea that they arise as lower bounds over classes of Bayesian probabilities.

BBN Rep. No. 3453, Bolt Beranek and Newman, Inc., Cambridge, Mass.

Research Report No. 25, Edinburgh: Department of Artificial Intelligence, August 1976.

Abstract: A data base system that supports natural language queries is not really natural if it requires the user to know how the data are represented. This paper defines a formalism, called conceptual graphs, that can describe data according to the user’s view and access data according to the system’s view. In addition, the graphs can represent functional dependencies in the data base and support inferences and computations that are not explicit in the initial query.IBM Journal of Research and Development 20:4, pp. 336-357.

Rep. No. 3438, Bolt Beranek and Newman, Inc., Cambridge, Mass.