perm filename NINE.PUB[BIB,CSR]2 blob sn#527772 filedate 1980-08-05 generic text, type C, neo UTF8

COMMENT ā VALID 00010 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .require "setup.csr[bib,csr]" source file C00004 00003 %3STAN-CS-80-806:%1 C00008 00004 %3STAN-CS-80-807:%1 C00010 00005 %3AIM-337 (STAN-CS-80-808):%1 C00011 00006 %3AIM-338 (STAN-CS-80-809):%1 C00014 00007 %3STAN-CS-80-810:%1 C00015 00008 %3PVG-18 (STAN-CS-80-811):%1 C00018 00009 %3HPP-80-14 (STAN-CS-80-812):%1 C00021 00010 %3AIM-340 (STAN-CS-80-813):%1 C00026 ENDMK Cā; .require "setup.csr[bib,csr]" source file; .font A "math55"; .once center %3Stanford University Computer Science Reports %3List Number 9ā? 1980%1 @Listed here are abstracts of the most recent reports published by the Department of Computer Science at Stanford University. @%3Request Reports:%1 Complete the enclosed order form, and return the entire order form page (including mailing label) as soon as possible. In many cases we can print only a limited number of copies, and requests will be filled on a first come, first served basis as the reports become available. If the code (FREE) is printed on your mailing label, you will not be charged for hardcopy. This exemption from payment is limited primarily to libraries. (The costs shown include all applicable sales taxes. %2Please send no money now, wait until you get an invoice%1.) @%3Alternatively:%1 Copies of most Stanford CS Reports may be obtained by writing (about 2 months after the "%2Most Recent CS Reports%1" listing) to %2National Technical Information Service%1, 5285 Port Royal Road, Springfield, Virginia 22161. Stanford Ph.D. theses are available from %2University Microfilms%1, 300 North Zeeb Road, Ann Arbor, Michigan 48106. .skip %3STAN-CS-80-806:%1 .once preface 0 @%2On the Approximate Solution of Hyperbolic Initial-Boundary Value Problems%1 by William M. Coughran, Jr. (Thesis, 177 pages, June 1980) @Hyperbolic initial-boundry value problems arise in a number of scientific disciplines, such as meteorology, ocanography, geophysics, aerodynamics, acoustics, and magnetohydrodynamics. These problems usually cannot be solved analytically, so approximate methods must be used. Unfortunately, the construction of stable finite difference approximations is a subtle matter, which often confuses the practitioner; the existing theories for establishing the well-posedness of continuous initial-boundary value problems and the stability of discrete analogs involve the verification of complicated algebraic conditions. Moreover, the stability theory fo discrete initial-boundary value problems in more than one space dimension is not well developed. @In this thesis, the existing stability theory for discrete initial-boundary value problems, which has only been applied to (essentially) salar model problems, is used to analyze the stability of some %22 %4x %22%1 model problems, not written in characteristic variables; it is noted that the most accurate interior/boundary difference scheme combinations are the least stable to perturbations in the coefficients. (A practical numerical procedure for verifying the stability of discrete initial-boundary value problems is also introduced.) The stability results for %22 %4x %22%1 systems can be used in the stability analysis of larger systems where characteristics occur only singly and in pairs; in particular, discretizations of the wave equation, the shallow water equations, and the Eulerian equations for gas dynamics, which involve boundary conditions written in "natural" variables, are examined. The stability theory is also extended to multi-dimensional initial-bondary value problems by means of the concept of "tangential dissipativity"; as an application, a tangentially dissipative leap-frog metho is shown to be stable with Euler boundary conditions for a two-dimensional wave equation problem. The viability and limitations of the theory are demonstrated with some computational experiments. Finally, combining stability results with accuracy considerations, various approximations and boundary conditions are ranked. .skip %3STAN-CS-80-807:%1 .once preface 0 @%2Path-Regular Graphs%1 by David W. Matula and Danny Dolev (39 pages, June 1980) @A graph is vertex-[edge-]path-regular if a list of shortest paths, allowing multiple copies of paths, exists where every pair of vertices are the endvertices of the same number of paths and each vertex [edge] occurs in the same number of paths of the list. The dependencies and independencies between the various path-regularity, regularity of degree, and symmetry properties are investigated. We show that every connected vertex-[edge-]symmetric graph is vertex-[edge-]path-regular, but not conversely. We show that the product of any two vertex-path-regular graphs is vertex-path-regular but not conversely, and the iterated product %2G %4x %2G %4x * * * x %2G%1 is edge-path-regular if and only if %2G%1 is edge-path-regular. An interpretation of path-regular graphs is given regarding the efficient design of concurrent communication networks. .skip %3AIM-337 (STAN-CS-80-808):%1 .once preface 0 @%2Basic Research in Artificial Intelligence and Foundations of Programming%1 by John McCarthy (Principal Investigator), Thomas Binford, David Luckham, Zohar Manna, Richard Weyhrauch (Associate Investigators) (75 pages, May 1980) @Recent research results are reviewed in the areas of formal reasoning, mathematical theory of computation, program verification, and image understanding. .skip %3AIM-338 (STAN-CS-80-809):%1 .once preface 0 @%2An Extention of Screw Theory and its Application to the Automation of Industrial Assemblies%1 by Jorgan S. Ohwovoriole (Thesis, 186 pages, April 1980) @Interest in mathematical models that adequately predict what happens in the process of assembling industrial parts has heightened in recent times. This is a result of the desire to automate the assembly process. Up to this point there has not been much success in deriving adequate mathematical models of the assembly process. @This thesis is an attempt to develop mathematical models of parts assembly. Assembly involves motion of bodies which generally contact each other during the process. Hence, we study the kinematics of the relative motion of contacting bodies. @Basic to the theory of assembly is the classical theory of screws which, however, required substantial extensions for this application. The thesis begins with a review of basic screw theory, including line geometry and reciprocal screw systems, and new and more general derivations of some of these screw systems. We then extend the screw theory by introducing such concepts as "repelling" and "contrary" screw pairs, and "total freedom." @Finally, we give a method of characterizing assemblies of industrial parts. Using the extended screw theory, we then analyze the "general peg-in-hole assembly" and subsequently give a mathematical description of this particular assembly. .skip %3STAN-CS-80-810:%1 .once preface 0 @%2Lower Bounds for algebraic Decision Trees%1 by J. Michael Steele and Andrew C. Yao (12 pages, July 1980) @A topological method is given for obtaining lower bounds for the height of algebraic decision trees. The method is applied to the knapsack problem where a %6W%2nā2)%1 bound is obtained for trees with bounded-degree polynomial tests, thus extending the Dobkin-Lipton result for linear trees. Applications to the convex hull problem and the distinct element problem are also indcated. Some open problems are discussed. .skip %3PVG-18 (STAN-CS-80-811):%1 .once preface 0 @%2An Extended Semantic Definition of Pascal for Proving the Absence of Common Runtime Errors%1 by Steven M. German (57 pages, June 1980) @We present an axiomatic definition of Pascal which is the logical basis of the Runcheck system, a working verifier for proving the absence of runtime errors such as arithmetic overflow, array subscripting out range, and accessing an uninitialized variable. Such errors cannot be detected at compile time by most compilers. Because the occurrence of a runtime error may depend on the values of data supplied to a program, techniques for assuring the absence of errors must be based on program specifications. Runchck accepts Pascal programs documented with assertions, and proves that the specifications are consistent with the program and that no runtime errors can occur. Our axiomatic definition is similar to Hoare's axiom system, but it takes into account certain restrictions that have not been considered in previous definitions. For instance, our definition accurately models uninitialized variables, and requires a variable to have a well defined value before it can be accessed. The logical problems of introducing the concept of uninitialized variables are discussed. Our definition of expression evaluation deals more fully with function calls than previous axiomatic definitions. @Some generalizations of our semantics are presented, including a new method of verifying programs with procedure and function parameters. Our semantics can be easily adopted to similar languages, such as ADA. @One of the main potential problems for the user of a verifier is the need to write detailed, repetitious assertions. We develop some simple logical properties of our definition which are exploited by Runcheck to reduce the need for such detailed assertions. .skip %3HPP-80-14 (STAN-CS-80-812):%1 .once preface 0 @%2Knowledge Engineering: The Applied Side of Artificial Intelligence%1 by Edward A. Feigenbaum (14 pages, ? 1980) @Expert System research is an emerging area of computer science that exploits the capabilities of computers for symbolic manipulation and inference to solve complex and difficult reasoning problems at the level of performance of human experts. The methods of this area are designed to acquire and represent both the formal and the informal knowledge that experts hold about the tasks of their disciplin. Numerous applications to science, engineering, and medicine have been accomplished. Expert System projects represent applied artificial intelligence research, though they also make salient numerous fundamental research issues in the acquisition, representation, and utilization of knowledge by computer programs. Knowledge engineering approaches promise significant cost savings in certain applications; intelligent computer-based aids for practitioners in fields whose knowledge is primarily nonmathematical; and the elucidation of the heuristic knowledge of experts -- the largely private knowledge of practice. There are major problems of knowledge engineering including the shortage of adequate computer equipment, the shortage of trained specialists in applied artificial intelligence, the scientific base for adequate knowledge acquisition, and the lack of sustained funding. .skip %3AIM-340 (STAN-CS-80-813):%1 .once preface 0 @%2Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover}%1 by Hans Peter Moravec (Thesis, 174 pages, September 1980) @The Stanford AI lab cart is a card-table sized mobile robot controlled remotely through a radio link, and equipped with a TV camera and transmitter. A computer has been programmed to drive the cart through cluttered indoor and outdoor spaces, gaining its knowledge about the world entirely from images broadcast by the onboard TV system. @The cart determines the three dimensional location of objects around it, and its own motion among them, by noting their apparent relative shifts in successive images obtained from the moving TV camera. It maintains a model of the location of the ground, and registers objects it has seen as potential obstacles if they are sufficiently above the surface, but not too high. It plans a path to a user-specified destination which avoids these obstructions. This plan is changed as the moving cart perceives new obstacles on its journey. @The system is moderately reliable, but very slow. The cart moves about one meter every ten to fifteen minutes, in lurches. After rolling a meter, it stops, takes some pictures and computes for a long time. Then it plans a new path, and executes a little of it, and pauses again. @The program has successfully driven the cart through several 20 meter indoor courses (each taking about five hours) complex enough to necessitate three or four avoiding swerves. A less sucessful outdoor run, in which the cart swerved around two obstacles but collided with a third, was also done. Harsh lighting (very bright surfaces next to very dark shadows) resulting in poor pictures, and movement of shadows during the cart's creeping progress, were major reasons for the poorer outdoor performance. These obstacle runs have been filmed (minus the very dull pauses).