To every 3-dimensional scene there correspond as many 2-dimensional pictures as there are possible vantage points for the camera. It is, however, possible to construct pictures for which there is no corresponding scene containing physically -realizable objects. Pictures of such'impossible objects' can be useful in giving insight into the constraints or grammatical rules associated with the'language' of pictures, just as nonsense sentences can be useful in illustrating the rules of other languages. Impossible objects have been used by psychologists (Penrose and Penrose 1958) to create visual illusions which successfully challenge the ability of our perceptual systems to synthesize a 3-dimensional world from 2-dimensional information. The incompatibilities among the various portions of pictures of these objects are a novel way of testing our picture analysis procedures. The purpose of this paper is to demonstrate some possible decision procedures and to test them on pictures of both possible and impossible objects.

In this paper, we develop the algorithm, given in Plotkin (1970), for findingthe least generalization of two clauses, into a theory of inductive generalization.The types of hypothesis which can be formed are very simple. They allhave the form: (x)Px --> Qx.We have been guided by ideas from the philosophy of science, followingBuchanan (1966). There is no search for infallible methods of generatingtrue hypotheses. Instead we define (in terms of first-order predicate calculus)the notions of data and evidence for the data. Next, some formal criteria areset up for a sentence to be a descriptive hypothesis which is a good explanationof the data, given the evidence. We can then look for the best such hypothesis.Machine Intelligence 6

"In this paper we describe work on the recognition by computer of objects viewed by a TV camera. We have written a program which will recognize a range of objects including a cup, a wedge, a hammer, a pencil, and a pair of spectacles. A visual image, represented by a 64.× 64 array of light levels, is first partitioned into connected regions. These regions are chosen to have well-defined edges.Having chosen the regions, the program then computes properties of and relations between regions. Properties include shape as defined by Fourier analysis of the s–ψ equation of the bounding curve. A typical relation between regions is the degree of adjacency.Finally, the program matches the actual relational structure of the regions of the picture with ideal relational structures representing various objects, using a heuristic search procedure, and selects that object whose relational structure best matches the actual picture."In B.Meltzer and D.Michie (Eds.), Machine intelligence 6. New York: Elsevier, 377-396

New York: McGraw-Hill.

Amsterdam: North-Holland.

New York: American Elsevier.

Artificial Intelligence, Vol. 2, pp. 79-116, 1971.

Ph.D. dissertation "Bi-directional and heuristic search in path problems" (Stanford, Computer Science, 1970) summarized in this article in Machine Intelligence 6 (1971).In the uni-directional algorithms, the search proceeds from an initial nodeforward until the goal node is encountered. Problems for which the goal nodeis explicitly known can be searched backward from the goal node. Analgorithm combining both search directions is bi-directional.This method has not seen much use because book-keeping problems werethought to outweigh the possible search reduction. The use of hashingfunctions to partition the search space provides a solution to some of theseimplementation problems. However, a more serious difficulty is involved.To realize significant savings in bi-directional search, the forward andbackward search trees must meet in the 'middle' of the space. The potentialbenefits from this technique motivates this paper's examination of thetheoretical and practical problems in using bi-directional search.

Inference systems Τ and search strategies E for T are distinguished from proof procedures β = (T,E) The completeness of procedures is studied by studying separately the completeness of inference systems and of search strategies. Completeness proofs for resolution systems are obtained by the construction of semantic trees. These systems include minimal α-restricted binary resolution, minimal α-restricted M-clash resolution and maximal pseudo-clash resolution. Certain refinements of hyper-resolution systems with equality axioms are shown to be complete and equivalent to refinements of the pararmodulation method for dealing with equality. The completeness and efficiency of search strategies for theorem-proving problems is studied in sufficient generality to include the case of search strategies for path-search problems in graphs. The notion of theorem-proving problem is defined abstractly so as to be dual to that of and" or tree. Special attention is given to resolution problems and to search strategies which generate simpler before more complex proofs. For efficiency, a proof procedure (T,E) requires an efficient search strategy E as well as an inference system T which admits both simple proofs and relatively few redundant and irrelevant derivations. The theory of efficient proof procedures outlined here is applied to proving the increased efficiency of the usual method for deleting tautologies and subsumed clauses. Counter-examples are exhibited for both the completeness and efficiency of alternative methods for deleting subsumed clauses. The efficiency of resolution procedures is improved by replacing the single operation of resolving a clash by the two operations of generating factors of clauses and of resolving a clash of factors. Several factoring methods are investigated for completeness. Of these the m-factoring method is shown to be always more efficient than the Wos-Robinson method. The University of Edinburgh

Full text available for a fee. "The use of augmented transition network grammars for the analysis of natural language sentences is described. Structure-building actions associated with the arcs of the grammar network allow for the reordering, restructuring, and copying of constituents necessary to produce deep-structure representations of the type normally obtained from a transformational analysis, and conditions on the arcs allow for a powerful selectivity which can rule out meaningless analyses and take advantage of semantic information to guide the parsing. The advantages of this model for natural language analysis are discussed in detail and illustrated by examples. An implementation of an experimental parsing system for transition network grammars is briefly described." Communications of the ACM, Vol. 13, No. 10, October, 1970, pp. 591-606 (reprinted in RNLP: 71-88).