Summary of Stanford Ph.D. dissertation, Computer Science Dept. Stanford University (1977).Artificial Intelligence 12(2): 73-119.

This article examines the process of specifying a question-answering help facility in the context of UNIX mail. The specification was based upon experimental expert-user facilitative dialogues. These dialogues were analyzed using a classification scheme developed for the purpose. The scheme provides a metalanguage for describing patterns of intent and rhetorical structure in dialogue. Using the scheme as a tool, common patterns in expert-user dialogue emerged, providing insights into both tutoring strategy and the linguistic forms required to generate help output.

A constraint network representation is presented for a combinatorial search problem: finding values for a set of variables subject to a set of constraints. A theory of consistency levels in such networks is formulated, which is related to problems of backtrack tree search efficiency. An algorithm is developed that can achieve any level of consistency desired, in order to preprocess the problem for subsequent backtrack search, or to function as an alternative to backtrack search by explicitly determining all solutions.

Most resolution theorem provers convert a theorem into clause form before attempting to find a proof. The conventional translation of a first-order formula into clause form often obscures the structure of the formula, and may increase the length of the formula by an exponential amount in the worst case. We present a non-standard clause form translation that preserves more of the structure of the formula than the conventional translation. This new translation also avoids the exponential increase in size which may occur with the standard translation. We show how this idea may be combined with the idea of replacing predicates by their definitions before converting to clause form.

A new system for the analysis of aerial photographs of suburban areas is presented. In this system, regions are characterized by various spectral and spatial features such as brightness, color, size, shape, texture, and spatial relationships with other regions. The analysis proceeds from a global survey of the picture to the detailed analysis of specific regions. The former process extracts several kinds of characteristic regions which are supposed to include specific objects by using knowledge-free picture processing programs. In the detailed analysis, several object-detection programs perform parallel analysis of extracted characteristic regions in detail to recognize objects such as crop fields, woods, roads, and houses.

It can be seen that a great deal of worthwhile material has now been generated about computer chess. There is also quite a bit of nonsense by persons who have never built a program. Several groups with excellent programs have done little publishing, although I can hardly blame them since their work requires much time and is usually unsupported by any funding agencies. Certain staples have given rise to duplication: All but one of the books published explain the depth-first alpha-beta procedure. We expect that by far the largest portion of our readers will be scientists interested in updating their knowledge of the subject.

A model of a text processing package is described which is based on elementary set theory. This is used to describe procedures for computing indexes, concordances, and collocations. Aspects of the implementation of the model are given.

As scientists interested in studying the phenomenon of “intelligence”, we first choose a view of Man, develop a theory of how intelligent behavior is managed, and construct some models which can test and refine that theory. The view we choose is that Man is a processor of symbolic information. The theory is that sophisticated cognitive tasks can be cast as searches or explorations, and that each human possesses (and efficiently accesses) a large body of informal rules of thumb (or heuristics) which constrain his search. The source of what we colloquially call “intelligence” is seen to be very efficient searching of an a priori immense space. Some computational models which incorporate this theory are described.

An analysis of the alpha-beta pruning algorithm is presented which takes into account both shallow and deep cut-offs. A formula is first developed to measure the average number of terminal nodes examined by the algorithm in a uniform tree of degree n and depth d when ties are allowed among the bottom positions: specifically, all bottom values are assumed to be independent identically distributed random variables drawn from a discrete probability distribution. A worst case analysis over all possible probability distributions is then presented by considering the limiting case when the discrete probability distribution tends to a continuous probability distribution. The branching factor of the alpha-beta pruning algorithm is shown to grow with n as Θ(n/lnn), therefore confirming a claim by Knuth and Moore that deep cut-offs only have a second order effect on the behavior of the algorithm.

This paper presents a body of program synthesis knowledge dealing with array operations, space reutilization, the divide-and-conquer paradigm, conversion from recursive paradigms to iterative paradigms, and ordered set enumerations. Such knowledge can be used for the synthesis of efficient and in-place sorts including quicksort, mergesort, sinking sort, and bubble sort, as well as other ordered set operations such as set union, element removal, and element addition. The knowledge is explicated to a level of detail such that it is possible to codify this knowledge as a set of program synthesis rules for use by a computer-based synthesis system. The use and content of this set of programming rules is illustrated by the methodical synthesis of bubble sort, sinking sort, quicksort, and mergesort.