perm filename THIRTN.MSS[BIB,CSR]1 blob sn#605118 filedate 1981-08-11 generic text, type T, neo UTF8

@make(PublicationOrderForm,Number 13,AnnouncementDate "August 1981") @begin[center] List Number 13 @end[center] @Entry(Code "STAN-CS-81-855", Title "Deductive Synthesis of the Unification Algorithm", Author "Zohar Manna and Richard Waldinger", Price "$3.55", FREE, Note "51 pages", Date "June 1981") The @i[deductive approach] is a formal program-construction method in which the derivation of a program from a given specification is regarded as a theorem-proving task. To construct a program whose output satisfies the conditions of the specification, we prove a theorem stating the existence of such an output. The proof is restricted to be sufficiently constructive so that a program computing the desired output can be extracted directly from the proof. The program we obtain is applicative and may consist of several mutually recursive procedures. The proof constitutes a demonstration of the correctness of this program. To exhibit the full power of the deductive approach, we apply it to a nontrivial example--the synthesis of a @i[unification algorithm]. Unification is the process of finding a common instance of two expressions. Algorithms to perform unification have been central to many theorem-proving systems and some programming-language processors. The task of deriving a unification algorithm automatically is beyond the power of existing program-synthesis systems. In this paper, we use the deductive approach to derive an algorithm from a simple, high-level specification of the unification task. We will identify some of the capabilities required of a theorem-proving system to perform this derivation automatically. @Entry(Code "STAN-CS-81-856", Title "An Organization for Programs in Fluid Domains", Author "Richard Paul Gabriel", Price "",FREE, Note "190 pages", Date "May 1981") An organization for very large artificial intelligence programs is presented with a detailed example in the area of natural language generation. The concept of a @i[fluid domain] is defined and shown to introduce constraints on the type of program organization required in such domains. The organization is a community of @i[stratifications] which communicate with each other in a fairly loose manner. Each stratification is a hierarchy of individuals, called @i[units], organized in meta-object/object relationships; these relationships allow observation and description of some units by others. It is shown that a great deal of power obtains from organizations of this type and from the interactions between the objects that exist in such systems. Further, this organization is demonstrated to be a valuable method of viewing both intelligence and the programming structures needed to produce intelligence. @Entry(Code "STAN-CS-81-857", Title "Query Optimization by Semantic Reasoning", Author "Jonathan Jay King", Price "$5.85", FREE, Note "128 pages", Date "May 1981") This thesis presents a new approach to the problem of database query optimization, called @i<semantic query optimization>. The goal of semantic query optimization is to produce a semantically equivalent query that is less expensive to process than the original query. The knowledge used to transform a query is the same knowledge used to insure the @i<semantic integrity> of the data stored in the database. A system called @b<QUIST> (@b<QUery Improvement through Semantic Transformation>) is described that carries out semantic query optimization for an important class of relational database queries. For many queries, QUIST can achieve substantial reductions in the cost of retrieval. It does this at a negligible cost for its analysis by relying on heuristics based on knowledge of database access and structure. @Entry(Code "STAN-CS-81-858", Title "The Bit Operation Complexity of Approximate Evaluation of Matrix and Polynomial Products Using Modular Arithmetic", Author "V. Ya. Pan", Price "$2.20", FREE, Note "6 pages", Date "June 1981") The approximate evaluation with a given precision of matrix and polynomial products is performed using modular arithmetic. The resulting algorithms are numerically stable. At the same time they are as fast as or faster than the algorithms with arithmetic operations over real or complex numbers. @Entry(Code "STAN-CS-81-859", Title "The Additive and Logical Complexities of Linear and Bilinear Arithmetic Algorithms", Author "V. Ya. Pan", Price "$2.65", FREE, Note "21 pages", Date "June 1981") @blankspace(2.5 inch) @Entry(Code "STAN-CS-81-860", Title "Computing the Controllability/Observability Decomposition of a Linear Time-Invariant Dynamic System, A Numerical Approach", Author "Daniel Boley", Price "$4.45", FREE, Note "81 pages", Date "June 1981") We examine various numerical properties involved in computing the complete Controllability-Observability (Kalman) Decomposition for a linear time-invariant dynamic system, of the form @begin(center) x=@i[A]x + @i[B]u y=@i[C]x @end(center) where @i[A, B, C] are matrices (@i[A] square), and u, x, y are vector functions of time. In particular, we discuss the numerical stability, the cost, and the particular advantages of several algorithms. We also examine several ways to measure ill-conditioning in the data. @Entry(Code "STAN-CS-81-861", Title "Symbolic Reasoning Among 3-D Models and 2-D Images", Author "Rodney A. Brooks", Price "$7.45", FREE, Note "181 pages", Date "June 1981") An implemented and operational model-based vision system is described. Examples are given of its interpretation of images, including extraction of three-dimensional parameters from monocular images. Advances are presented in representation for geometric modeling of objects and object classes, in techniques for manipulating non-linear symbolic algebraic constraints, in geometric reasoning in incompletely specified situations, and in constructing algebraic constraints from image measurements. Both generic object classes and specific objects are represented by volume models which are independent of viewpoint. Complex real-world object classes are modeled. Variations in size, structure and spatial relations within object classes can be modeled. New spatial reasoning techniques are described which are useful both for prediction within a vision system, and for planning within a manipulation system. New approaches to prediction and interpretation are introduced, based on the propagation of symbolic constraints. Predictions are two-pronged. First, prediction graphs provide a coarse filter for hypothesizing matches of objects to image features. Second, prediction graphs contain instructions on how to use measurements of image features to deduce three-dimensional information about tentative object interpretations. Interpretation proceeds by merging local hypothesized matches, subject to consistent derived implications about the size, structure and spatial configuration of the hypothesized objects. Prediction, description and interpretation proceed concurrently, from coarse object subpart and class interpretations of images, to fine distinctions among object subclasses, and more precise three-dimensional quantification of objects. @Entry(Code "STAN-CS-81-862", Title "The Lower Bounds on the Additive Complexity of Bilinear Problems in Terms of Some Algebraic Quantities", Author "V. Ya. Pan", Price "$2.10", FREE, Note "4 pages", Date "June 1981") The lower bounds on the additive complexity of a bilinear problem are expressed in terms of the rank of the problem and also as a minimum number of elementary steps for the transformation of the identity matrix into a strongly regular one. @Entry(Code "STAN-CS-81-863", Title "A Programming and Problem-Solving Seminar", Author "Donald E. Knuth and Allan A. Miller", Price "$4.50", FREE, Note "84 pages", Date "June 1981") This report contains edited transcripts of the discussions held in Stanford's course CS 204, Problem Seminar, during autumn quarter 1980. Since the topics span a large range of ideas in computer science, and since most of the important research paradigms and programming paradigms came up during the discussions, the notes may be of use to graduate students of computer science at other universities, as well as to their professors and to professional people in the ``real world.'' The thesis also addresses an important issue in current automatic planning research: production not just of a correct solution but of a ``good'' one, by means of an efficient problem solver. Semantic query optimization advances the notion of a @i<problem reformulation> step for problem-solving programs. In this step, equivalent statements of the original problem are sought, one of which may have a better solution than the original problem. This method avoids explicit and possibly costly analysis of efficiency factors during planning itself. @Entry(Code "STAN-CS-81-864", Title "Three Short Essays on Decisions, Reasons, and Logics", Author "Jon Doyle", Price "$2.60", FREE, Note "19 pages", Date "May 1981") This report collects together three short, survey-level essays introducing related approaches to decision-making, reasoning, and logic. The first essay, @i[Making Difficult Decisions,] was read to the Stanford Computer Forum on February 5, 1981. The following two essays, @i[Dependencies and Assumptions] (written with Johan de Kleer) and @i[Non-Deductive Reasoning and Non-Monotonic Logics,] are versions of articles to appear in the @i[Handbook of Artificial Intelligence] (A. Barr, P. Cohen and E. Feigenbaum, eds.). @Entry(Code "STAN-CS-81-865", Title "Toward A Unified Logical Basis for Programming Languages", Author "Chih-sung Tang", Price "$2.65", not available Note "21 pages", Date "June 1981") In recent years, more and more computer scientists have been paying attention to temporal logic, since there are many properties of programs that can be described only by bringing the time parameter into consideration. But existing temporal logic languages, such as Lucid, in spite of their mathematical elegance, are still far from practical. I believe that a practical temporal-logic language, once it came into being, would have a wide spectrum of applications. XYZ/E is a temporal-logic language. Like other logic languages, it is a logic system as well as a programming language. But unlike them, it can express all conventional data structures and control structures, nondeterminate or concurrent programs, even programs with branching-time order. We find that the difficulties met in other logic languages often stem from the fact that they try to deal with these structures in a higher level. XYZ/E adopts another approach. We divide the language into two forms: the internal form and the external form. The former is lower level, while the latter is higher. Just as any logic system contains rules of abbreviation, so also in XYZ/E there are rules of abbreviation to transform the internal form into the external form, and vice versa. These two forms can be considered to be different representations of the same thing. We find that this approach can ameliorate many problems of formalization. @Entry(Code "STAN-CS-81-866", Title "Verifying the Absence of Common Runtime Errors in Computer Programs", Author "Steven M. German", Price "$7.40", FREE, Note "179 pages", Date "June 1981") The Runcheck verifier is a working prototype system for proving the absence of runtime errors such as arithmetic overflow, array subscripting out of range, accessing an uninitialized variable, and dereferencing a null pointer. Such errors cannot be detected at compile time by most compilers. Runcheck accepts Pascal programs documented with assertions and proves that the assertions are consistent with the program and that no runtime errors can occur. The thesis begins by presenting an axiomatic definition of Pascal for proving the absence of runtime errors. Our definition is similar to Hoare's axiom system, but it takes into account certain restrictions which have not been considered in previous axiomatic definitions. The definition is based on a special predicate, DEF(x), which is true if x has a properly initialized value. We discuss the problem of introducing uninitialized variables in an axiomatic definition, and construct models of the data types from nonstandard models of the integers to justify our new approach to uninitialized variables. The final section draws on experience with Runcheck and the Stanford Pascal Verifier to discuss some of the major issues concerning verification and software reliability, including how verification can contribute to reliability even if absolute correctness cannot be obtained, and which applications of program verification may be feasible for large programs. @Entry(Code "STAN-CS-81-867", Title "ADAM - An Ada based Language for Multi-processing", Author "Luckham, Larsen, Stevenson and von Henke", Price "$4.15", FREE, Note "71 pages", Date "July 1981") Adam is an experimental language derived from Ada. It was developed to facilitate study of issues in Ada implementation. The two primary objectives which motivated the development of Adam were: to program supervisory packages for multitask scheduling, and to formulate algorithms for compilation of Ada tasking. Adam is a subset of the sequential program constructs of Ada combined with a set of parallel processing constructs which are lower level than Ada tasking. In addition, Adam places strong restrictions on sharing of global objects between processes. Import declarations and propagate declarations are included. A compiler has been implemented in Maclisp on a DEC PDP-10. It produces assembly code for a PDP-10. It supports separate compilation, generics, exceptions, and parallel processes. Algorithms translating Ada tasking into Adam parallel processing have been developed and implemented. An experimental compiler for most of the final Ada language design, including task types and task rendezvous constructs, based on the Adam compiler, is presently available on PDP-10's. This compiler uses a procedure call implementation of task rendezvous, but will be used to develop and study alternate implementations. @Entry(Code "STAN-CS-81-868", Title "The Last Whole Errata Catalog", Author "Donald E. Knuth", Price "$3.25", FREE, Note "42 pages", Date "July 1981") This list of errata and addenda to The Art of Computer Programming supplements previous listings published in Stanford reports CS55l (1976) and CS7l2 (1979). It includes the first corrections and changes to the second edition of volume two (published January, 1981) as well as to the most recent prints of volumes one and three (first published in 1975). In addition to the errors listed here, about half of the occurrences of `which' in volumes one and three should be changed to `that'. @Entry(Code "STAN-CS-81-869", Title "Stanford Computer Science Comprehensive Examination", Author "Carolyn Tajnai", Price "$15.00", FREE, Note "225 pages", Date "July 1981") The Stanford Computer Science Comprehensive Examination was conceived Spring Quarter 1971/72 and since then has been given winter and spring quarters each year. The @i[Comp] serves several purposes in the department. There are no course requirements in the Ph.D. and the Ph.D. Minor programs, and only one (CS293, @i[Computer Laboratory]) in the Master's program. Therefore, the @i[Comp] fulfills the breadth and depth requirements. The Ph.D. Minor and Master's student must pass at the Master's level to be eligible for the degree. For the Ph.D. student it serves as a "Rite of Passage;" the exam must be passed at the Ph.D. level by the end of six quarters of full-time study (excluding summers) for the student to continue in the program. This report is a collection of comprehensive examinations from Winter Quarter 1978/79 through Spring Quarter 1980/81. ERRATA: STAN-CS-81-836, Zohar Manna and Amir Pnueli, @i[Verification of Concurrent Programs, Part I: The Temporal Framework]