Lists provide the most obvious and natural representation of literals because lists perfectly reflect function nesting structure. A list is also a reasonable representation of a set, in particular of a clause. Lists, however, can consume large amounts of space, and cause frequent garbage collections. We shall present in this paper a representation of clauses and literals which is as natural as lists but far more compact. We achieve this economy by sharing the structure of the parents of a resolvent in our representation of the resolvent. A clause is a set of literals; but throughout this paper we shall speak of the literals of a clause as having an order. That is, we shall speak of the first, second, etc., literal of a clause.

INTRODUCTION If let loose, resolution theorem-provers can waste time in many ways. They can continually rearrange the multiplication brackets of an associative multiplication operation or replace terms t by ones like f(f(f(t, e), e), e) where f is a multiplication function and e is its identity. Generally they continually discover and misapply trivial lemmas. Global heuristics using term complexity do not help much and ad hoc devices seem suspicious. On the other hand, one would like to evaluate terms when possible, for example we would want to replace 5 4 by 9. More generally one would like to have liberty to simplify, to factorise and to rearrange terms. The obvious way to deal with an associative multiplication would be to imitate people, and just drop the multiplication brackets. However used or abused the basic facts involved in such manipulations form an equational theory, T, that is, a theory all of whose sentences are universal closures of equations. Under certain conditions, we will be able to build the equational theory into the rules of inference. The resulting method will be resolution-like, the difference being that concepts are defined using provable equality between terms rather than literal identity. Therefore the set of clauses expressing the theory will not be among the input clauses, so no time will be wasted in the misapplication of trivial lemmas, since the rules will not waste time in this way.

INTRODUCTION In May 1971 the Mark 1.5 Edinburgh robot system went on-line as a complete hand-eye system. Two years earlier the Mark 1 device had been connected to the ic L 4130 computer of the Department of Machine Intelligence and Perception. The Mark 1 (Barrow and Salter 1970) had been little more than a semi-mobile T.V. camera, with coarse picture sampling (64 x 64 points, 16 levels), a limited range of movement over a three-foot diameter circular platform, and a pair of touch-sensitive bumpers. Within eighteen months we had developed suitable basic software, and a teachable' program capable of recognizing irregular objects via the However, the restrictions upon movement, the limited range of actions which could modify the'world', and the shortcomings of the video system, made more advanced work difficult. Plans were therefore laid for the construction of the Mark 2 device. The Mark 2 robot system will possess moderately sophisticated eyes and a hand which can manipulate objects with a reasonable degree of precision. The present equipment thus represents a useable system, not yet up to full Mark 2 specification, but considerably more useful than the Mark 1. DESIGN CONCEPTS It is important that the complete system should be as self-reliant as possible. If it depends much upon human assistance to pre-process information or to put things right when they go astray, it is all too easy in one's research to avoid the central issues of a problem, and produce a'solution' which does not survive when confronted by real situations. In the Mark 1 device we implemented a suggestion from Derek Healy that when a robot is complicated and linked to a fixed computer, and its world is simple, it is better to keep the robot still and move the world. From its own point of view, the robot cannot tell whether it or the world moves, and one can simulate free movement in a restricted area.

INTRODUCTION Research in machine vision is an important activity in artificial intelligence laboratories for two major reasons. First, understanding vision is a worthy subject for its own sake. The point of view of artificial intelligence allows a fresh new look at old questions and exposes a great deal about vision in general, independent of whether man or machine is the seeing agent. Second, the same problems found in understanding vision are of central interest in the development of a broad theory of intelligence. Making a machine see brings one to grips with problems like that of knowledge interaction on many levels and of large system organization. In vision these key issues are exhibited with enough substance to be nontrivial and enough simplicity to be tractable. Both goals are framed in terms of a world of bricks, wedges, and other simple shapes like those found in children's toy boxes. Good purposeful description is often fundamental to research in artificial intelligence, and learning how to do description constitutes a major part of our effort in vision research. This essay begins with a discussion of that part of scene analysis known as body finding. The intention is to show how our understanding has evolved away from blind fumbling toward substantive theory. Finding groups of objects and using the groups to get at the properties of their members illustrates concretely how some of the ideas about systems work out in detail. The topic of learning follows. Discussing learning is especially appropriate here not only because it is an important piece of artificial intelligence theory but also because it illustrates a particular use for the elaborate analysis machinery dealt with in the previous sections. Finally a scenario exhibits the flavor of the system in a situation where a simple structure is copied from spare parts. The body-finding story begins with an ad hoc but crisp syntactic theory and ends in a simple, appealing theory with serious semantic roots. In this the history of the body-finding problem seems paradigmatic of vision system progress in general. Adolfo Guzman started the work in this area (Guzman 1968). I review his program here in order to anchor the discussion and show how better programs emerge through the interaction of observation, experiment, and theory. The task is simply to partition the observed regions of a scene into distinct bodies.

An operator is characterized by a precondition statement describing the conditions under which it may be applied, and lists of statements describing its effects. Specifically, the effect of an operator is to remove from the model all statements matching forms on the operator's'delete list', and to add to the model all statements on the operator's'add list'.

When x is printed it is (3) and y when printed is (2, 3) rather than (2, 1) as it would have been had the last assignment left it undisturbed. How are we to prove assertions about such programs?

The study of perception is divided among many established sciences: physiology, experimental psychology and machine intelligence; with several others making contributions. But each of the contributing sciences tends to have its own concepts, and ways of considering problems. Each -- to use T. S. Kuhn's term (1962) -- has its own'paradigm', within which its science is respectable. This can make co-operation difficult, as misunderstandings (and even distrust) can be generated by paradigm differences. This paper is a plea to consider perceptual phenomena from many points of view, and to consider whether a general paradigm for perception might be found.

We describe how to design simple contentaddressable memories, functioning in parallel, which can do this and which, in some sense, can generalise about the stored data. Secondly, we consider how certain graphical representations of data may be suitable for use in efficient serial search strategies. We indicate how such structures can be used in diagnosis when the availability or cost of tests to be applied cannot be determined in advance. The type of parallel system to be considered is to store descriptions of a set of patterns, and is then to be used to supplement an incomplete description of a newly presented pattern by matching it against those in store. If this partial description matches one or more of the stored patterns then we would like the memory to provide us with the partial description that these patterns share. If the new pattern does not match any in store then we expect that the information supplied will be according to the relationships between the pattern presented and those in store. The information that we require our memory to provide when given an incomplete description as an address is therefore more than just the response'yes' or'no'. In this respect our type of system differs from content-addressable parallel memories used in computer technology, and for the same reason its capabilities exceed that of a switching network which is designed to respond positively when the states of its input channels attain one of a number of combinations of binary values (Richards 1971, Renwick and Cole 1971). This paper generalises the work of Willshaw (1972) to ensembles which conform to few or no logical constraints.

INTRODUCTION In this paper we compare three models of transformational grammar: the mathematical model of Ginsburg and Partee (1969) as applied by Salomaa (1971), the mathematical model of Peters and Ritchie (1971 and forthcoming), and the computer model of Friedman et al. (1971). All of these are, of course, based on the work of Chomsky as presented in Aspects of the Theory of Syntax (1965). We were led to this comparison by the observation that the computer model is weaker in three important ways: search depth is not unbounded, structures matching variables cannot be compared, and structures matching variables cannot be moved. All of these are important to the explanatory adequacy of transformational grammar. Both mathematical models allow the first, they each allow some form of the second, one of them allows the third. We were interested in the mathematical consequences of our restrictions. The comparison will be carried out by reformulating in the computer system the most interesting proofs to date of the ability of transformational grammars to generate any recursively enumerable set.

And-or graphs and theorem-proving graphs determine the same kind of search space and differ only in the direction of search: from axioms to goals, in the case of theorem-proving graphs, and in the opposite direction, from goals to axioms, in the case of and-or graphs. Bi-directional search strategies combine both directions of search. We investigate the construction of a single general algorithm which covers uni-directional search both for and-or graphs and for theorem-proving graphs, bi-directional search for path-finding problems and search for a simplest solution as well as search for any solution. We obtain a general theory of completeness which applies to search spaces with infinite or-branching. In the case of search for any solution, we argue against the application of strategies designed for finding simplest solutions, but argue for assigning a major role in guiding the search to the use of symbol complexity (the number of symbol occurrences in a derivation).