Search

Research resulting in papers or theses accepted or completed includes (1) the A* search algorithm, (2) search within parsing, (3) search using expectation, and (4) parallel implementation of semantic nets. Research areas where papers are now being written up include (a) parallel implementation of a test-and-treatment algorithm and (b) knowledge evaluation with uncertainties. Research continues in areas ranging from foundations of search theory (e.g., search with limited resources) to applications of search methodology (e.g., search within parsing).

Sequences of queries to a database system can have structure. Recognizing this structure is a kind of parsing , analogous to the parsing of sentences. We present two rather different approaches to recognition for exploitation. The first is a rule-based system that examines superficial aspects of a query sequence to postulate preferences between sets mentioned in the queries. The second is a deeper, but more limited model based on decision theory, which assigns utilities and suitability probabilities to individual set items, and attempts to explain set preferences on that basis. Both of these methods have disadvantages, and their performance is difficult to analyze because of the fuzzy nature of the application, but it is hoped they can form the basis for more comprehensive man-machine interfaces.

Parser design lags behind linguistic theory. While modern transformational grammar has largely abandoned complex, language-specific rule systems in favor of modular subsystems of principles and parameters, the rule systems that underlie existing natural-language parsers are still large, detailed and complicated. The shift to modular theories in linguistics took place because of the scientific disadvantages of such rule systems. Those scientific ills translate into engineering maladies that make building natural-language systems difficult. The cure for these problems should be the same in parser design as it was in linguistic theory. The shift to modular theories of syntax should be replicated in parsing practive. parser should based its actions on interacting modules of principles and parameters rather than a complex, monolithic rule system. If it can be successfully carried out, the shift will make it easier to build natural-language systems because it will shorten and simplify the language descriptions that are needed for parsing. It will also allow parser design to track new developments in linguistic theory. (Author)

This project is concerned with the architecture, design, and testing of VLSI Systems. The principal activities in this report period include: The Tree Machine; COPE, The Homogeneous Machine; Computational Arrays; Switch-Level Model for MOS Logic Design; Testing; Local Network and Designer Workstations; Self-timed Systems; Characterization of Deadlock Free Resource Contention; Concurrency Algebra; Language Design and Logic for Program Verification.

The Pattern Analysis Branch, Mapping, Charting and Geodesy (MC/G) Division, of the Naval Ocean Research and Development Activity (NORDA) has been involved over the past several years in the development of algorithms and techniques for computer recognition of free-form handprinted symbols as they appear on the Defense Mapping Agency (DMA) maps and charts. NORDA has made significant contributions to the automation of MC/G through advancing the state of the art in such information extraction techniques. In particular, new concepts in character (symbol) skeletonization, rugged feature measurements, and expert system-oriented decision logic have allowed the development of a very high performance Handprinted Symbol Recognition (HSR) system for identifying depth soundings from naval smooth sheets (accuracies greater than 99.5%). The study reported in this technical note is part of NORDA's continuing research and development in pattern and shape analysis as it applies to Navy and DMA ocean/environment problems. The issue addressed in this technical note deals with emerging areas of syntactic and semantic techniques in pattern recognition as they might apply to the free-form symbol problem.

This project consisted of a preliminary design and a partial implementation of a tool which modifies the existing Ada Compiler Validation Capability (ACVC) test set so it can be used to test evolving Ada compilers. The project evaluated the feasibility of repackaging each of test classes found in the ACVC and suggested methods for repackaging the tests. The tool developed uses a table-driven parser which parses the July 1980 proposed standard. In uses output from the parser to generate a representation of a test program. Once the representation is developed, unsupported language-features are removed from it. The remaining representation is output as a valid test program. (Author)

Programming a computer to write text which meets a prior need is a challenging research task. As part of such research, Nigel, a large programmed grammar of English, has been created in the framework of systemic linguistics begun by Halliday. In addition to specifying function and structures of English, Nigel has a novel semantic stratum which specifies the situations in which each grammatical feature should be used. The report consists of three papers on Nigel: an introductory overview, the script of a demonstration of its use in generation, and an exposition of how Nigel relates to the systemic framework. Although the effort to develop Nigel is significant both as computer science research and as linguistic inquiry the outlook of the report is oriented to its linguistic significance.

This project studied the possibility of establishing an Ada cross-compiler hosted on the CDC Cyber 6000 family and targeted to the zilog Z800. Initial work supports the feasibility of a complete implementation. The present front-end processor of the compiler is capable of parsing full Ada syntax and processing most declarations and executable statements. The back-end processor of the compiler is less complete than the front-end although it has sucessfully translated simple Ada programs. During initial development, the author discovered a new implementation technique that may be beneficial to other Ada implementors. Full implementation of this Ada compiler is projected for October 1983 and will be the subject of subsequent reports., See also Volume 2, AD-B072 338L.

This thesis involved the development of a top down recursive descent Ada recognizer. The recognizer accepts syntactically valid Ada programs and rejects those that are not. Basic concepts of compiler theory as they relate to syntax analysis were reviewed. Appropriate syntax diagrams were selected and transformed into program statements using a structured method. The software was developed with attention to software engineering practices. Uses for the recognizer as a programmers tool are discussed. The steps necessary to transform the recognizer into a compiler are discussed.

This report summarizes project work carried out at the Computer Science Laboratory of SRI International under Contract F30602-78-C-0031 with Rome Air Development Center during the period November 1977 - November 1981. The project has been concerned with the development of a programming environment (Rugged Jovial Environment)--with verification tools as a principal component--for the specification, development, and formal verification of programs in JOVIAL-J73. The term verification here refers to proof of correctness with respect to formal specification by the method of Floyd assertions. The effort on this project has ranged from fairly abstract work on formal models of computation (in particular, regarding the semantics of JOVIAL constructs) to practical techniques for implementing these models. This has resulted in the development of a user-friendly system, written in INTERLISP, with the aid of which it is possible to verify JOVIAL software of significant complexity. In addition to our primary project work, we developed several very usefull software tools of more general applicability. These tools are also described in the report.

This document describes the design and implementation of a programming support environment for the ADA language based on a syntax-directed editor and a program tree structure. Though the prototype compiler is limited to a small subset, the full ADA language is supported by the remainder of the environment. Most of the environment is driven by a language syntax description, and is therefore capable of processing virtually any programming language. The prototype syntax-directed environment demonstrates the ability to reduce programmer idle time during development by eliminating parsing and lexical analysis in the compiler. The program tree structure also allows for the development of superior programming environment tools. (Author)

This document describes an algorithm for incremental parsing of expressions in the context of syntax-directed editors for programming languages. Since a syntax-directed editor represents programs as trees and statements and expressions as nodes in trees, making minor modifications in an expression can be difficult. To make these changes in a typical syntax-directed editor, the user must understand the tree structure and type a number of tree-oriented construction and manipulation commands. This document describes an algorithm that allows the user to think in terms of the syntax of the expression as it is displayed on the screen (in infix notation) rather than in terms of its internal representation (which is effectively prefix), while maintaining the benefits of syntax-directed editing. The time and space complexities of the modifications for each new token are linear in the depth of the syntax tree.

Many non-specialists are intimidated by the mathematical appearance of most applicative, functional, and very-high-level languages. This report presents a simple notation that has an unintimidating, natural-language appearance and that can be adapted to a variety of languages. The paper demonstrates its use as an alternate syntax for LISP, PROLOG, Backus' FP, relational programming, and relational database retrievals. The grammar's eight productions can be handled by a simple recursive-descent parser. (Author)

We have constructed a local code generator for the VAX-11 using a parser-like instruction pattern matcher. The code generator replaces the second pass of the UNIX Portable C compiler. This paper describes the design of the code generator and the special considerations imposed by the pattern matching process. We summarize the structure of the machine description grammar and its associated semantic actions, as well as the tools we developed to manipulate the large VAX description. In our experience, this approach makes the instruction selection phase of the compiler easier and faster to implement, and more likely to be correct than traditional techniques., Sponsored in part by Grant NSF-MCS80-05144.

This report summarizes the research of BBN's ARPA-sponsored Knowledge Representation for Natural Language Understanding project during its fourth year. In it we report on advances, both in theory and implementation, in the areas of knowledge representation, natural language understanding, and abstract parallel machines. In particular, we report on theoretical advances in the knowledge representation system KL-ONE, extensions to the KL-ONE system, and new uses of KL-ONE in the domain of knowledge about graphic displays. We report on a design for a new prototype natural language understanding system, on issues in cascaded architectures for interaction among the components of a language system, and on a module for Lexical acquisition. In addition, we examine three topics in discourse: a new model of speaker meaning, which extends our previous work on speakers' intentions, an investigation of reference planning and identification, and a theory of 'one'-anaphora interpretation. Our discussion of abstract parallel machines reports on a class of algorithms that approximate Quillian's (49) ideas on the function of human memory. (Author), See also report dated Nov 1980, ADA092971.

Since English specifications and formal specifications of modules are complementary and since formal specifications require so much effort to write, our work is investigating application of artificial intelligence techniques to aid in the software specification process. The first area studied is comparing English descriptions with formal specifications of the same software module. This work is now complete; however, some of the examples will continue to serve as a guide to the software tool being constructed. The second area is suggesting modifications to formal specification languages, which would make them more understandable. In particular, we have been suggesting alternatives to logical quantifiers. The third and fourth areas deal with the syntactic and semantic components of an experimental software tool. Its purpose is to test our solutions to a handful of problems in transforming English descriptions to formal specifications under significant user assistance. In dealing with syntactic ambiguity, one of the solutions that many have spectulated about is the use of a semantic component to reject anomolous parses; we intend to test its effectiveness using the RUS grammar. When ambiguity is not resolved, questions must be presented to the user for his/her selection of the intended interpretation. Partial heuristics for this are part of the results of this year's effort. In addition, modification of the RUS parser and dictionary for the domain of software specification will continue during the next year.

In the first phase, the implementation of the FlexP parser was completed according to the design described in last year's annual report, and was evaluated through use in a gracefully interacting interface. This application showed: that FlexP was able to parse both grammatical and ungrammatical input according to a simple grammar of pattern-matching rewrite rules, that the bottom-up approach of FlexP was helpful in the case of ungrammatical input, and that a grammar suitable for use by FlexP could be defined in terms natural to the domain of interaction of the interface. However, the experimental use of FlexP also made it clear that FlexP had certain problems, largely due to the uniform nature of its grammar. In the second phase, the set of design choices on which FlexP was based was reviewed to determine if it was possible to resolve the problems that FlexP had without also losing the desirable aspects of its performance. This review led to the replacement of a single parsing strategy based on linear pattern matching with an approach based on multiple construction-specific parsing strategies. This approach was evaluated in a preliminary way through the construction of two small parsers, CASPAR and DYPAR, and was found to show considerable promise. Accordingly, design based on the same approach was begun for a more complete parser for restricted domain natural languages, and for a parser oriented towards an artificial command language of the type common in interactive user interfaces.

This document contains: a description of ORACLE SQL. Familiarity with the ORACLE manual is subsumed; SDL/DS features are described; a description of IDL and its relationship to the IDM commands; the correlation between SQL and the IDM features; additional IDM features not available within SQL; and unimplemented features of full SEQUEL.

This thesis describes the design and implementation of a language- independent reuseable code generator for Prime 400 and 50-Series computers. A code generator is the portion of a compiler that converts an internal representation of the semantics of a program into equivalent machine code. Construction of a code generator requires a major effort, so it should be done as infrequently as possible. One way to make this possible is to build a code generator that may be re-used from compiler to compiler. Several factors influence the design of such a code generator, including the nature of the communications channel between the code generator and the rest of the compiler, the structure of the information passed to the code generator (the 'intermediate form'), the form of output code desired, and finally the limitations of the machine architecture and existing systems software. The code generator implemented processes a high-level, tree-structured intermediate form, performing translation by case analysis and optimization by eliminating redundant load operations. It produces a stream of assembly language source code which may then be assembled, loaded, and executed. Experience with two compiler implementations has shown that the reusable code generator approach is feasibile. However, several improvements in the present code generator would be desirable. (Author)

A syntax directed editor is an editor oriented towards a particular language. This paper describes a general table-driven syntax directed editor and an algorithm for automatically generating a syntax directed editor for a language from a description of that language. Aside from the convenience of a syntax directed editor, it is also a very efficient parser. No syntactic error recovery is required since the editor does not permit the user to make syntactic errors. Some of the implications of syntax directed editors for data structure manipulation and two dimensional languages are briefly discussed. (Author)

Two syntactic methods for the recognition of seismic waveforms are presented in this paper. The seismic waveforms are represented by sentences (strings of primitives). Primitive extraction is based on a cluster analysis. Finite-state grammars are inferred from the training samples. The nearest-neighbor decision rule and error-correcting finite-state parsers are used for pattern classification. While both show equal recognition performance, the nearest-neighbor rule is much faster in computation speed. The classification of real earthquake/explosion data is presented as an application example. (Author)

Given a grammar G and a string sigma, all possible parses of sigma can be constructed by repeatedly applying the rules of G in parallel. This process creates a 'lattice graph' in which any directed path from the least element to the greatest element is a sentential form that occurs in a (partial) parse of sigma. Examples are given illustrating how, at least for some grammars, this process does not lead to a combinatorial explosion, and could thus be used to parse strings very rapidly if suitable parallel hardware were available. (Author)

Composite materials have come into use lately in aircraft construction because of their high strength and low weight. This report examines a method for computing the shielding effectiveness of a narrow slit in a composite material. This corresponds to a joint or seam between two composite panels. For low frequency incident fields, the composite can be effectively modelled as an infinitely thin impedance sheet. The literature on impedance sheets is reviewed and a general integral equation formulation for impedance sheets is described. Since only narrow slits (seams) are of practical interest, a quasi-static (low frequency) approach is developed. A dual integral equation is derived for the problem. The dual integral equation is reduced to a Fredholm second kind integral equation. This integral equation is solved by expanding the unknown in terms of Legendre polynomials. An analytic solution for the problem of a narrow slit in a perfectly conducting plane is also obtained. (Author)

This project involved defining an Ada pseudo-machine and developing an Ada to pseudo-code test translator. The translator's front end incorporates a table-driven parser that can parse the entire proposed-standard Ada language. The translator's semantic routines allow integer data objects, several control structures, procedures, functions, packages and tasks. These routines generate pseudo-code that is executed by an interpreter program included in the translator. The interpreter constitutes a complete description of the pseudo-machine whose architecture consists of multiple, stack-oriented processors that access a common memory. Interesting features of the project include the hash-coded symbol table that supports Ada's visibility rules and the pseudo-machine architecture that supports Ada's tasking. (Author)

A Pascal compiler is described whose target language is the lambda-calculus instead of some machine code. Although the lambda-calculus code generated by this complier can be executed by means of a lambda-expression reducer, the intended use of the translation is in proving programs correct. The complier is written in Pascal itself, and contains an attributed LL(1) parser of the complete standard Pascal language. The error recovery is quite elaborate. The code generalization is done for a large subset of the language, covering: assignments, compound, conditional and repetitive statements, procedures including recursive calls and global side effects, multidimensional arrays. This report contains a formal definition of the target language, a lambda-calculus model for the selected subset of Pascal, and a code-independent description of compilation algorithms including the complete LL(1) push-down automation.

When people use natural language in natural settings, they often use it ungrammatically, missing out or repeating words, breaking-off and restarting, speaking in fragments, etc.. Their human listeners are usually able to cope with these deviations with little difficulty. If a computer system wishes to accept natural language input from its users on a routine basis, it must display a similar indifference. In this paper, we outline a set of parsing flexibilities that such a system should provide. We go on to described FlexP, a bottom-up pattern-matching parser that we have designed and implemented to provide these flexibilities for restricted natural language input to a limited-domain computer system. (Author)

In recent years the Air Force has developed a standard programming language, J73, for use in embedded computer systems. Now that the Air Force has a considerable investment in systems that are currently being developed with J73, the Department of Defense has selected a high order programming language, Ada, that will become the standard for programming embedded computer systems throughout the Department of Defense. Also under development is the definition of a support environment for Ada. One of the tools of this support environment should be a translator that will produce Ada source programs from J73 source programs. The subject of this research project was the design and development of a Jovial (J73) to Ada Translator System (JATS). The resulting system accepts J73 programs and produces equivalent Ada programs to the extent possible while identifying segments of J73 code that were not translated. This project made use of language parsing techniques and various data structures to support the translation process. Several problem areas are identified with possible solutions. The translator system should be a useful tool in the transition from J73 to Ada. (Author)

We will trace a brief history of context-free parsing algorithms and then describe some representation issues. The purpose of this paper is to share our philosophy and experience in adapting a well-known context free parsing algorithm (Earley's algorithm and variations thereof) to the parsing of a difficult and wide ranging corpus of sentences. The sentences were gathered by Malhotra in an experiment which fooled businessmen users into thinking they were interacting with a computer, when they were actually interacting with Malhotra in another room. The Malhotra corpus is considerably more difficult than a second collection published by the LADDER Group. Both collections are given in the appendices. Section 4 compares empirical results obtained from these collections against theoretical predictions. (Author)

A syntactic method for the analysis of time-varying image patterns is proposed and studied. This method utilizes translation schema to model the time-varying properties of image patterns. A syntactic deformation model is first applied to transform the i-th image into the (i+1)-th image of an image sequence. Then the concept of translation in formal Language theory is used as a mechanism to characterize the dynamic process of the image sequence. A formulation of stochastic translation is also presented. A generalized syntax-directed tree translation model is proposed to handle high-dimensional patterns. The generalized model is compared with the conventional top-down and bottom-up tree translation models. A traffic monitoring problem is analyzed using the proposed tree translation model. Each input image is represented as a tree structure. The proposed tree translation model is used to model the variation of image content between consecutive images. A parsing algorithm for tree translation is applied to match moving objects (vehicles) in each pair of consecutive images. (Author)

Conventional parsing techniques use grammars as embedded procedural knowledge bases in mechanisms which are capable of translating words in the language defined into equivalent parse trees. The approach described in this paper uses context-free grammars as data allowing access to synthesis templates which enable the user to create and interact with parse trees directly. The advantages of this approach are the utility of human-oriented grammars, the dynamic interchangeability of language definitions, immediate error rejection, and the ability to handle partially complete parse trees. The design for a prototype programming environment using grammar-driven synthesis is presented. (Author)

BORIS is a story understanding and question answering system which involves the specification and interaction of many sources of knowledge. Unlike skimmers, which simply extract the gist of a story in a top-down manner and ignore everything else, BORIS attempts to understand everything that it reads to as great a depth as possible. This report focuses on how the BORIS program handles a complex story involving a divorce. (Author)

An ALGOL-like graphics oriented language and system was designed to provide a block-structured format to graphics programs. The system was developed with an LR(1) parsing procedure technique, and graphs are constructed using the DISSPLA software package as the 'host' to generate device-independent plot files. The language produces linear, bar and pie graphs, as well as having a text processor to draw a variety of character styles and fonts for documentation. (Author)

A severe software crisis is currently being experienced by the data processing community due to intolerable maintenance costs. A system is introduced to reduce those costs by the translation of existing COBOL software into HIBOL; a very high level language that is significantly easier to maintain. HIBOL, uses a single type of data object, called a flow, which is an indexed stream of data values. Computation is expressed as operations acting on flows. The translation process relies on a method for program abstraction developed by Richard Waters which expresses programs as a hierarchical structure, called an analyzed plan, in which control and data flow is made explicit. In this formalism, loops are expressed as a composition of stream operators acting on stream data flow. This paper discusses in detail how an analyzed plan for a COBOL program can be transmitted into a HIBOL program. It is currently possible to translated into HIBOL analyzed plans for a relatively small (but well defined) subset of COBOL programs. Suggestions are made as to how that subset could be expanded through further research. (Author), Sponsored in part by Contract N00014-75-C-0643 and Grant NSF-MCS79-12179.

The Ada language has been designated by the Department of Defense to replace the computer languages currently in use by the various services for tactical computer programs. This thesis modifies the Cornell Subset of Ada so that it is suitable for producing the LALR(1) grammar. Machine generated compiling tools such as LEX and YACC, available under the UNIX operating system, are then used to implement the scanner and the parser for this subset of Ada. (Author)

This report documents results of a 12-month R/D effort consisting in development of MATRES III, a language understanding system for automated generation of AIS data base elements. Section 1.0 discusses the need for a high-volume message processing technology in the I/W environment, and summarizes its current state of the art exemplified in MATRES II. Section 2.0 describes in detail the methodological approach adopted in MATRES III for analysis/description of event reports, and provides background information on conceptually relevant efforts. Section 3.0 provides an overview of message processing from raw text input to final output of event record in MATRES III. Section 4.0 presents MATRES III model data based system, and Section 5.0 provides guidelines for continuing development of message processing technology. Examples of message segments and event records synthesized from these segments are presented in Appendices A and B, respectively. (Author)

This thesis attempts to clarify some of the difficulties behind evaluating the performance of natural language processors. It also proposes an evaluation method that is designed to be systematic and thorough. The method relies on considering a natural language processor from three viewpoints in the light of several taxonomies of issues relevant to natural language processing. Finally, an evaluation is described of PLANES, a natural language database query system.

This report summarizes the major progress made during the support of NATO Research Grant 1639--On Hybrid Approaches to Pattern Recognition; Automatic Inspection by Lots in the Presence of Classification Errors; and Visual Screening of Integrated Circuits for Metallization Faults by Pattern Analysis Methods., Prepared in cooperation with George Washington Univ., Washington, DC. French Scientific Mission.

CCIS is a revolutionary new hardware and software system for Navy data management, giving a command center the capability for providing high quality information to its commander as an aid in his decision making. It allows processing of natural language queries to proceed at the same time as dynamic data update. It provides extensibility so that the computer can 'understand' the commander's individualized description of data received in the command center from standard static and dynamic sources. It also allows those dynamic sources to be customized uniformly to the particular command center. (Author)

The formal specification, design, implementation, and verification of a compiler for a Pascal-like language is described. All components of the compilation process such as scanning, parsing, type checking, and code generation are considered. The implemented language contains most control structures of Pascal, recursive procedures and functions, and jumps. It provides user defined data types including arrays, records, and pointers. A simple facility for input-output is provided. The target language assumes a stack machine including a display mechanism to handle procedure and function calls. The compiler itself is written in Pascal Plus, a dialect of Pascal accepted by the Stanford verifier. The Stanford verifier is used to give a complete formal machine checked verification of the compiler. One of the main problem areas considered is the formal mathematical treatment of programming languages and compilers suitable as input for automated program verification systems. Several technical and methodological problems of mechanically verifying large software systems are considered. Some new verification techniques are developed, notably methods to reason about pointers, fixed points, and quantification. These techniques are of general importance and are not limited to compiler verification. The result of this research demonstrates that construction of large correct programs is possible with the existing verification technology. It indicates that verification will become a useful software engineering tool in the future. Several problem areas of current verification systems are pointed out and areas for future research are outlined. (Author)

This paper provides both a precise specification of a subset of FORTRAN 66 and FORTRAN 77 and a specification of the verification condition generator we have implemented for that subset. Our subset includes all the statements in FORTRAN 66 except the following: READ, WRITE, REWIND, BACKSPACE, ENDFILE, FORMAT, EQUIVALENCE, DATA, and BLOCK DATA. We place some restrictions on the remaining statements; however, our subset includes certain uses of COMMON, adjustable array dimensions, function subprograms, subroutine subprograms with side effects, and computed and assigned GO TOs. Unusual features of our system include a syntax checker that enforces all our syntactic restrictions on the language, the thorough analysis of aliasing, the generation of verification conditions to prove termination, and the generation of verification conditions to ensure against such run-time errors as array bound violations and arithmetic overflow. We have used the system to verify several running FORTRAN programs. We present one such program and discuss its verification. (Author)

The main emphasis of grant work was bringing software that was reliably working on a DECsystem-10 into reliable operation on the Virginia Tech VM/CMS system. This work is best viewed as preparation for the substantial work of the grant. Work was also directed toward achieving two objectives: (1) Modify an incremental program verification system to accept APL programs. The main work here was to isolate code in the verifier that is specific to the syntax of the programming language in which the programs were written in a single SIMULA class so that is could be easily modified for different languages. (2) Completing the implementation of an APL expression evaluator based on a formal semantics of APL and verifying this implementation with respect to the formal semantics. During this period, the objective was to complete a verified implementation of an APL epxression evaluator and to have an interactive verifier for APL expressions working correctly by about August 15, 1980. These two pieces of software were then to be used to conduct a number of experiments that would aid in the design of a verifier for all of APL.

Generalization and memory are part of natural language understanding. As people read stories describing various situations they are able to recall similar episodes form memory and use them as a basis to form generalizations about the way such situations normally occur. This thesis describes an integrated system for language understanding IPP (Integrated Partial Parser), that encompasses the ability to generalize and record information in long-term memory as well as conceptual analysis. IPP is a program that learns about the world by reading stories taken from newspapers and th UPI news wire, adding information from these stories to memory, and making generalizations that describe specific situations. It uses the generalizations that it has made to help in understanding future stories. As it reads stories, IPP adds them to its permanent memory. If it locates similar stories in memory as it does this, then it attempts to make generalizations that describe the similarities among the events. Such generalizations form the basis for organizing events in memory and understanding later stories. IPP also includes a procedure for confirming generalizations as further stories are read. In order to analyze the text that it reads, IPP makes extensive use of top-down, predictive processing. As it processes a story, IPP accesses memory in an attempt to identify generalizations describing stereotypical situations that can provide predictions to be used in understanding. Such use of memory to provide top-down context results in a robust and efficient understanding system. (Author)

BBN's ARPA project in Knowledge Representation for Natural Language Understanding is aimed at developing techniques for computer assistance to a decision maker in understanding a complex system or situation using natural language control of an intelligence graphics display. The work that we have been doing falls into three classes: fluent natural language understanding in a graphics context - including helpful systems that go beyond mere passive execution of literal instructions, fundamental problems of knowledge representation and use, and abstract parallel algorithms for knowledge base inferential operations. In this report, we will give a brief summary of the activities of this research project during the past year, in particular in the areas of research on parallel algorithms and VLSI, research on the KL-ONE system, and research on natural language understanding. In addition, we document publications written, presentations given and workshops attended.

This final report is intended to be a summary of the research on Natural Language Data Base Query. It has been the goal of this research to determine a minimal set of techniques sufficient to provide a practical natural language capability for data base query. This report summarizes the basic requirements for such a capability and suggests techniques for meeting these requirements. As such, this report is in effect, a specification of the minimal functionality for a practical natural language data base query capability.

The RUS system (Bobrow, 1978) is a new parser for English which allows semantically directed parsing by interleaving calls to a separate, independent semantic component with syntatic processing in a case-oriented ATN grammar. This thesis discusses the syntactic component (RUS), the points at which it calls a semantic component, and the nature of the syntactic-semantic interaction occurs, the nature of the interaction, and the structure of the dictionary are the only assumptions placed on the semantic component. (Author)

We explore techniques for systematically deriving programs from specifications. The goal of this exploration is a better understanding of the development of algorithms. Thus, the intention is not to develop a theory of programs, concerned with the analysis of existing programs, but instead to develop a theory of programming, dealing with the process of constructing new programs. Such a theory would have practical benefits both for programming methodology and for automatic program synthesis. We investigate the derivation of programs by program transformation techniques. By expanding an ordinary language of recursion equations to include a generalized procedure construct (the expression procedure), our ability to manipulate programs in that language is greatly facilitated. The expression procedure provides a means of expressing information not just about the properties of individual program elements, but also about the way they relate to each other. A set of three operations -- abstraction, application, and composition -- for transforming programs in this extended language is presented. We prove using operational semantics that these operations preserve the strong equivalence of programs. The well-known systems of Burstall and Darlington and of Manna and Waldinger are both based on an underlying rule system that does not have this property.

This report summarizes a project entitled 'The Enhancement of Datamodule 1.' The focus of this project is to study the Datacomputer's (MARILL and STERN) performance in its role as a datamodule in SDD-1 and as a DBMS in other command and control applications. The goal of this study is to produce a set of potential performance enhancements and an analysis of their expected effect on overall Datacomputer performance. Some of the proposed enhancements would be subsequently implemented in the Datacomputer. During the reporting period, the model of Datacomputer performance constructed previously during this project was used to analyze performance in the Advanced Command and Control Architecture Testbed (ACCAT). The Datacomputer was instrumented to produce extensive performance data at runtime. The results of this work have indicated which parts of the system are bottlenecks and this, in turn, is suggesting potential enhancements. In addition, the instrumented Datacomputer has been used in other performance work for ARPA.

Program acquisition is the transformation of a program specification into an executable, but not necessarily efficient, program that meets the given specification. This thesis presents a solution to one aspect of the program acquisition problem; the incremental construction of program models from informal descriptions. The key to the solution is a framework for incremental program acquisition that includes a formal language for expressing program fragments that contain informalities; a control structure for the incremental recognition and assimilation of such fragments; and a knowledge base of rules for acquiring programs specified with informalities. The thesis describes a LISP based computer system called the Program Model Builder (PMB), which receives informal program fragments incrementally and assembles them into a very high level program model that is complete, semantically consistent, unambiguous, and executable. The program specification comes in the form of partial program fragments that arrive in any order and may exhibit such informalities as inconsistencies and ambiguous references. Possible sources of fragments are a natural language parser or a parser for a surface form of the fragments. PMB produces a program model that is a complete and executable computer program. the program fragment language used for specifications is a superset of the language in which program models are built. This program modelling language is a very high level programming language for symbolic processing that deals with such information structures as sets and mappings. The recognition paradigm used by PMB is a form of subgoaling that allows the parts of the program to be specified in an order chosen by the user, rather than dictated by the system., Prepared in cooperation with Systems Control, Inc., Palo Alto, CA. Dept. of Computer Science, Contract N00014-79-C-0127, Rept. no. SCI-ICS-U79-2.

When bounded cellular automata are used as acceptors for formal languages, the number of time steps required to accept a string sigma is at least true value of sigma, except in certain trivial cases, since the distinguished cell's state after t steps cannot depend on the initial states of the cells at distances t from it. However, if the automaton is allowed to shrink (i.e., cells are deleted, and their predecessors become directly connected to their successors), language acceptance in less than linear time becomes possible. (Author)

The report describes a SIMULA program that parses character strings according to a grammar preprocessed by a parser generator. The program does not furnish error recovery. This report provides all information necessary to use the program including a detailed description of the format of the parse tree produced and the symbol table employed. (Author)