We will define the notions of abstract theorem-proving graph, abstract theorem-proving problem g and search strategy E for g. These concepts generalize the usual tree (or graph) searching problem and admit Hart, Nilsson and Raphael (1968) and Pohl (1969) theories of heuristic search. In particular the admissibility and optimality theorems of Hart, Nilsson and Raphael generalize for the classes 0 and 0" of diagonal search strategies for abstract theorem-proving problems. In addition the subclass au of 0 is shown to be optimal for 2. Implementation of diagonal search is treated in some detail for theorem-proving by resolution rules (Robinson 1965). SEARCH STRATEGIES, COMPLETENESS AND EFFICIENCY Completeness and efficiency of proof procedures can be studied only in the context of search strategies. A system T of inference rules and axioms can be complete or incomplete for a given class of intended interpretations. Similarly a search strategy E for T may or may not be complete for ...

Engeler, E., Proof theory and the accuracy of computations (to appear).

The equivalence problem for program schemes, or for programs, is reduced to the proving of a theorem in second-order logic. This work extends Manna's first-order logic reductions. Some examples of the technique are given together with a suggested method for obtaining proofs in special cases by firstorder methods. INTRODUCTION Several workers in recent years have considered using techniques and ideas of various mathematical theories of computation for proving interesting results about computer programs. This paper is concerned with two of these approaches.

COGNITIVE PROCESSES: METHODS AND MODELS 17 Steps towards a model of word selection.

Konig's infinity lemma 61,90, 161 spanning tree of, see tree Kowalski 176-8, 181 Graph Traverser program 450,456-7 Kripke 493-5, 501 Greanias 376, 381 Green, B. F. jnr.

F(n,$) as introduced here corresponds to A.N.Prior's (1957, 1968) expression Fir.

INTRODUCTION The problem of reducing the line-like elements of a digitized picture to idealized thin lines is of general interest in pattern recognition. As early as 1957 the idea of obtaining a thin-line representation of certain patterns was suggested (Kirsch et al. 1957); recently McCormick (1963) and Narasimhan (1964) have described computer programs for doing this (for use in particular on bubble chamber photographs), and similar work has been done in character recognition, for example by Deutsch (1967). Blum (1964) has put forward an approach for dealing with more general shapes. In this the boundary of a shape is considered as being the source of a wavefront. The points at which wavefronts originating at different parts of the boundary first meet form a'skeleton' which, with a function giving the time taken for the wavefront to reach each point of the skeleton, completely defines the original shape. Programs for generating this skeleton for digitized pictures have been described by Rosenfeld and Pfaltz (1966), and also by Philbrick (1966).

Two types of expression of empirical interest have been studied: sentences in English and other'natural' languages, and programs written in some high-level procedural language like ALGOL. Expressions in these languages consist of sets of elements (words and characters) co-ordinated with one another according to the sensorily manifest relationship'alongside', more commonly termed'followed by'.

The program contains a rough theory of mass spectrometry which is still in its formative stages.

ABSTRACT This paper shows how a question-answering system can be constructed using first-order logic as its language and a resolution-type theorem-prover as its deductive mechanism. A working computer-program, Q A3, based on these ideas is described. The performance of the program compares favorably with several other general question-answering systems. The type of questionanswering system considered in this paper is ideally one having the following features: 1. A language general enough to describe any reasonable questionanswering subjects and express desired questions and answers. This paper argues the case for formal methods to achieve such a system and presents one particular approach in detail. The name'question-answering system' requires clarification. The system described above might be named an'advice taker' or a'multi-purpose problem-solving system' or'general problem-solving system'. McCarthy (1958) proposed using formal languages and deduction to construct such a system, and suggested allowing the user to give hints or advice on how to answer a question; he referred to the proposed system as an'advice taker'. Research on'multi-purpose' or'general problem-solving' tends to differ from questionanswering as described above by placing more emphasis on solving deeper, more difficult problems and less emphasis on user interaction, formality, and efficient retrieval of relevant facts from a large data base. The situation is further confused by the use of'question-answering' to refer sometimes to natural language systems, sometimes to information retrieval systems having little deductive ability, and sometimes to systems with deductive ability limited to the propositional calculus. It is important to emphasize the distinction between general versus specialpurpose question-answering. If the class of questions asked of a system is small, completely specified in advance, and concerned with a particular subject area, such as the question-answering system of Green, Wolf, Chomsky, and Laughery (1963) concerned with baseball, or that of Lindsay (1963) concerned with family relations, then we shall call such a system'specialpurpose'. Frequently the goal in designing a special-purpose system is to achieve good performance, measured in terms of running speed and memory utilization. In this case the best approach may be first to construct a special data base or memory that is optimized for that subject area and question class, and then to write special question-answering subroutines that are optimized for the particular data base and question class.