IJCAI 1, 557-567.

In Meltzer, Bernard and Donald Michie (Eds.), Machine Intelligence 4. Edinburgh University Press.

Note: PDF of full volume downloadable by clicking on title above (32.8 MB). Selected individual chapters available from the links below.CONTENTSINTRODUCTORY MATERIALMATHEMATICAL FOUNDATIONS1 Program scheme equivalences and second-order logic. D. C. COOPER 32 Programs and their proofs: an algebraic approach.R. M. BURSTALL and P. J. LANDIN 173 Towards the unique decomposition of graphs. C. R. SNOW andH. I. SCOINS 45THEOREM PROVING4 Advances and problems in mechanical proof procedures. D. PRAWITZ 595 Theorem-provers combining model elimination and Tesolution.D. W. LOVELAND 736 Semantic trees in automatic theorem-proving. R. KOWALSKI andP. J. HAYES 877 A machine-oriented logic incorporating the equality relation.E. E. SIBERT 1038 Paramodulation and theorem-proving in first-order theories withequality. G. ROBINSON and L. Wos 1359 Mechanizing higher-order logic. J. A. ROBINSON 151DEDUCTIVE INFORMATION RETRIEVAL10 Theorem proving and information retrieval. J. L. DARLINGTON 17311 Theorem-proving by resolution as a basis for question-answeringsystems. C. CORDELL GREEN 183MACHINE LEARNING AND HEURISTIC PROGRAMMING12 Heuristic dendral: a program for generating explanatory hypothesesin organic chemistry. B. BUCHANAN, G. SUTHERLAND andE. A. FEIGENBAUM 20913 A chess-playing program. J. J. SCOTT 25514 Analysis of the machine chess game. I. J. GOOD 26715 PROSE—Parsing Recogniser Outputting Sentences in English.D. B. VIGOR, D. URQUHART and A. WILKINSON 27116 The organization of interaction in collectives of automata. 285V. I. VARSHAVSKY COGNITIVE PROCESSES: METHODS AND MODELS17 Steps towards a model of word selection. G. R. Kiss 31518 The game of hare and hounds and the statistical study of literaryvocabulary. S. H. STOREY and M. A. MAYBREY 33719 The holophone —recent developments. D. J. WILLSHAW andH. C. LONGUET-HIGGINS 349PATTERN RECOGNITION20 Pictorial relationships — a syntactic approach. M. B. CLOWES 36121 On the construction of an efficient feature space for optical characterrecognition. A. W. M. COOMBS 38522 Linear skeletons from square cupboards. C. J. HILDITCH 403PROBLEM-ORIENTED LANGUAGES23 Absys 1: an incremental compiler for assertions; an introduction.J. M. FOSTER and E. W. ELCOCK 423PRINCIPLES FOR DESIGNING INTELLIGENT ROBOTS24 Planning and generalisation in an automaton/environment system.J. E. DORAN 43325 Freddy in toyland. R. J. POPPLESTONE 45526 Some philosophical problems from the standpoint of artificialintelligence. J. MCCARTHY and P. J. HAYES 463INDEX 505 Machine Intelligence Workshop

Note: PDF of full volume downloadable by clicking on title above (26 MB). Selected individual chapters available from the links below. CONTENTSINTRODUCTION MATHEMATICAL FOUNDATIONS1 The morphology of prex—an essay in meta-algorithmics. J. LAS KS 32 Program schemata. M. S. PATE RSON 193 Language definition and compiler validation. J. J. FLORENTIN 334 Placing trees in lexicographic order. H. I.S COINS 43 THEOREM PROVING5 A new look at mathematics and its mechanization. B. M ELTZER 636 Some notes on resolution strategies. B. MELTZER 717 The generalized resolution principle. J. A. ROBINSON 778 Some tree-paring strategies for theorem proving. D.LUCKHAM 959 Automatic theorem proving with equality substitutions andmathematical induction. J. L. D ARLINGTON 113 MACHINE LEARNING AND HEURISTIC PROGRAMMING10 On representations of problems of reasoning about actions.S.AMAREL 13111 Descriptions. E.W.ELCOCK 17312 Kalah on Atlas. A.G.BELL 18113 Experiments with a pleasure-seeking automaton: J. E. DORAN 19514 Collective behaviour and control problems. V.I.VARSHAVSKY 217 MAN—MACHINE INTERACTION15 A comparison of heuristic, interactive, and unaided methods ofsolving a shortest-route problem. D.MICHIE, J. G. FLEMING andJ. V.OLDFIELD 24516 Interactive programming at Carnegie Tech. A.H.BOND 25717 Maintenance of large computer systems—the engineer's assistant.M.H.J.BAYLIS 269 COGNITIVE PROCESSES: METHODS AND MODELS18 The syntactic analysis of English by machine. J.P.THORNE,P.BRATLEY and H.DEWAR 28119 The adaptive memorization of sequences. H.C.LONOUETHIGGINSand A.ORTONY 311 PATTERN RECOGNITION20 An application of Graph Theory in pattern recognition.C.J.HILDITCH 325 PROBLEM-ORIENTED LANGUAGES21 Some semantics for data structures. D. PARK 35122 Writing search algorithms in functional form. R.M.BURSTALL 37323 Assertions: programs written without specifying unnecessaryorder. J.M.FOSTER 38724 The design philosophy of Pop-2. R.J.POPPLESTONE 393 INDEX 403 Machine Intelligence Workshop

In D. Michie (ed.), Machine Intelligence 3, Edinburgh University Press, pp. 281-309,

A recognition algorithm is exhibited whereby an arbitrary string over a given vocabulary can be tested for containment in a given context-free language. A special merit of this algorithm is that it is completed in a number of steps proportional to the “cube” of the number of symbols in the tested string. As a byproduct of the grammatical analysis, required by the recognition algorithm, one can obtain, by some additional processing not exceeding the “cube” factor of computational complexity, a parsing matrix—a complete summary of the grammatical structure of the sentence. It is also shown how, by means of a minor modification of the recognition algorithm, one can obtain an integer representing the ambiguity of the sentence, i.e., the number of distinct ways in which that sentence can be generated by the grammar. The recognition algorithm is then simulated on a Turing Machine.

Research on question answering by Raphael, Black, and Elliott, and our own work on Protosynthex II has shown that question-answering algorithms can be most easily written if the text source is in the form of simple, explicitly structured sets of subject-verb-nominal strings. Question-answering algorithms that have thus far been developed include word- and structure-matching operations and some few logical inference functions. All of the systems cited have in some fashion limited their input language to simple subject-verb-nominal strings, thus eliminating many problems of syntactic analysis and providing a normalized form for language data.

In Part I, four ostensibly different theoretical models of induction are presented, in which the problem dealt with is the extrapolation of a very long sequence of symbols—presumably containing all of the information to be used in the induction. Almost all, if not all problems in induction can be put in this form. Some strong heuristic arguments have been obtained for the equivalence of the last three models. One of these models is equivalent to a Bayes formulation, in which a priori probabilities are assigned to sequences of symbols on the basis of the lengths of inputs to a universal Turing machine that are required to produce the sequence of interest as output. Though it seems likely, it is not certain whether the first of the four models is equivalent to the other three.

In J. A. Fodor and J. J. Katz, The structure of language. Englewood Cliffs, N.J.: Prentice- Hall, 137-151.

A statement in a spoken language may be regarded as a one-dimensional string of symbols used to communicate an idea from the speaker to a listener. The dimensionality of the statement is limited by the need for presenting words in a single time sequence. However, evidence indicates that most information and ideas are not stored by people in one-dimensional arrays isomorphic to these linear strings. This implies that a speaker must use certain complex information manipulating processes to transform the stored information to a linear output string, and that a listener, in order to "understand" the speaker, must use another set of processes to decode this linear string. In order for communication to take place, the information map of both the listener and the speaker must be approximately the same, at least for the universe of discourse.