perm filename SEPT.LST[DOC,CSR] blob sn#372396 filedate 1978-08-28 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00014 PAGES C REC PAGE DESCRIPTION C00001 00001 C00003 00002 .REQUIRE "ABSTRA.CMD[BIB,CSR]" SOURCE FILE C00004 00003 .once center C00006 00004 %3STAN-CS-78-661 VARIATIONS OF A PEBBLE GAME ON GRAPHS%1 C00008 00005 %3STAN-CS-78-662 NEW ALGORITHMS IN BIN PACKING%1 C00010 00006 %3STAN-CS-78-663 SOFTWARE RESTYLING IN GRAPHICS AND PROGRAMMING LANGUAGES%1 C00012 00007 %3STAN-CS-78-664 ANALYSIS OF A NEW ALGORITHM FOR ONE-DIMENSIONAL MINIMIZATION%1 C00014 00008 %3STAN-CS-78-665 SCALD: STRUCTURED COMPUTER-AIDED LOGIC DESIGN%1 C00016 00009 %3STAN-CS-78-666 THE SCALD PHYSICAL DESIGN SUBSYSTEM%1 C00017 00010 %3HPP-78-7 DISTRIBUTED PROBLEM SOLVING: THE CONTRACT NET APPROACH%1 C00020 00011 %3HPP-78-10 BAOBAB, A PARSER FOR A RULE-BASED SYSTEM USING A SEMANTIC GRAMMAR%1 C00023 00012 %3STAN-CS-78-669 ON THE OPTIMALITY OF LINEAR MERGE%1 C00025 00013 %3STAN-CS-78-670 INFORMATION BOUNDS ARE WEAK IN THE SHORTEST DISTANCE PROBLEM%1 C00028 00014 .next page C00031 ENDMK C⊗; .REQUIRE "ABSTRA.CMD[BIB,CSR]" SOURCE FILE .next page .once center %3MOST RECENT CS REPORTS - SEPTEMBER 1978%1 @Listed below are abstracts of the most recent reports published by the Computer Science Department of Stanford University. @TO REQUEST REPORTS:##Check the appropriate places on the enclosed order form, and return the entire order form page (including mailing label) by September 8, 1978. In many cases we can print only a limited number of copies, and requests will be filled on a first come, first serve basis. In 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. PLEASE SEND NO MONEY NOW, WAIT UNTIL YOU GET AN INVOICE.) @ALTERNATIVELY: Copies of most Stanford CS Reports may be obtained by writing (about 2 months after MOST RECENT CS REPORTS listing) to NATIONAL TECHNICAL INFORMATION SERVICE, 5285 Port Royal Road, Springfield, Virginia 22161. Stanford Ph.D. theses are available from UNIVERSITY MICROFILMS, 300 North Zeeb Road, Ann Arbor, Michigan 48106. .begin nofill %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-661 VARIATIONS OF A PEBBLE GAME ON GRAPHS%1 %3Authors:%1 John R. Gilbert & Robert Endre Tarjan .end %3Abstract:%1@We exame two variations of a one-person pebble game played on directed graphs, which has been studied as a model of register allocation. The black-white pebble game of Cook and Sethi is shown to require as many pebbles in the worst case as the normal pebble game, to within a constant factor. For another version of the pebble game, the problem of deciding whether a given number of pebbles is sufficient for a given graph is shown to be complete in polynomial space. .break .begin nofill No. of pages: 23 Cost: $ 2.35 %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-662 NEW ALGORITHMS IN BIN PACKING%1 %3Author:%1 Andrew Chi-Chih Yao .end %3Abstract:%1@In the bin-packing problem a list L of n numbers are to be packed into unit-capacity bins. For any algorithm S, let r(S) be the maximum ratio S(L)/L%6*%1 for large L%6*%1, where S(L) denotes the number of bins used by S and L%6*%1 denotes the minimum number needed. In this paper we give an on-line O(n log n) -time algorithm RFF with r(RFF) = 5/3, and an off-line polynomial-time algorithm RFFD with r(RFFD) = (11/9)-%2ε %1for some fixed %2ε %1> 0. These are strictly better respectively than two prominent algorithms -- the First-Fit (FF) which is on-line with r(FF) = 17/10, and the First-Fit-Decreasing (FFD) with r(FFD) = 11/9. Furthermore, it is shown that any on-line algorithm S must have r(S) %2≥ %13/2. We also discuss the question "how well can an O(n) -time algorithm perform?", showing that, in the generalized d-dimensional bin-packing, any O(n) -time algorithm S must have r(S) %2≥ %1d. .break .begin nofill No. of pages: 50 Cost: $ 3.10 %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-663 SOFTWARE RESTYLING IN GRAPHICS AND PROGRAMMING LANGUAGES%1 %3Author:%1 Eric Grosse .end %3Abstract:%1@The value of large software products can be cheaply increased by adding restyled interfaces that attract new users. As examples of this approach, a set of graphics primitives and a language precompiler for scientific computation are described. These two systems include a general user-defined coordinate system instead of numerous system settings, indention to specify block structure, a modified indexing convention for array parameters, a syntax for n-and-a-half-times-round loops, and engineering format for real constants; most of all, they strive to be as small as possible. .break .begin nofill No. of pages: 30 Cost: $ 2.55 %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-664 ANALYSIS OF A NEW ALGORITHM FOR ONE-DIMENSIONAL MINIMIZATION%1 %3Authors:%1 Peter Bjorstad & Jorge Nocedal .end %3Abstract:%1@Davidon has recently introduced a new approach to optimization using the idea of nonlinear scaling. In this paper we study the algorithm that results when applying his ideas to the one-dimensional case. We show that the algorithm is locally convergent with R-order equal 2 and compare its convergence properties with the method of cubic interpolation. .break .begin nofill No. of pages: 18 Cost: $ 2.20 %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-665 SCALD: STRUCTURED COMPUTER-AIDED LOGIC DESIGN%1 %3TR-152%1 %3Authors:%1 T. M. McWilliams & L. C. Widdoes, Jr. .end %3Abstract:%1@SCALD, a graphics-based hierarchical digital logic design system, is described and an example of its use is given. SCALD provides a total computer-aided design environment which inputs a high-level description of a digital system, and produces output for computer-aided manufacture of the system. SCALD has been used in the design of an operational, 15-MIPS, 5500-chip ECL-10k processor. .break .begin nofill No. of pages: 39 Cost: $ 2.80 %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-666 THE SCALD PHYSICAL DESIGN SUBSYSTEM%1 %3TR-153%1 %3Authors:%1 T. M. McWilliams & L. C. Widdoes, Jr. .end %3Abstract:%1@The SCALD physical design subsystem is described. SCALD supports the automatic construction of ECL-10k logic on wire wrap cards from the output of a hierarchical design system. Results of its use in the design of an operational 15-MIPS 5500-chip processor are presented and discussed. .break .begin nofill No. of pages: 28 Cost: $ 2.50 %4-------------------------------------------------------------------------------------%1 %3HPP-78-7 DISTRIBUTED PROBLEM SOLVING: THE CONTRACT NET APPROACH%1 %3Authors:%1 Reid G. Smith & Randall Davis .end %3Abstract:%1@We describe a problem solver based on a group of processor nodes which cooperate to solve problems. In a departure from earlier system, we view task distribution as an interactive process, a discussion carried on between a node with a task to be executed and a group of nodes that may be able to execute the task. This leads to the use of a control formalism based on a contract metaphor, in which task distribution corresponds to contract negotiation. We also consider the kinds of knowledge that are used in such a problem solver, the way that the knowledge is indexed within an individual node, and distributed among the group of nodes. We suggest two primary methods of indexing the knowledge (referred to as "task-centered" and "knowledge-source centered"), and show how both methods can be useful. We illustrate the kind of information that must be passes between nodes in the distributed processor in order to carry out task and data distribution. We suggest that a common internode language is required, and that task-specific "expertise" reqired by processor node can be obtained by internode transfer of procedures and data. We consider the operation of a distributed sensor net as an instantiation of the issues we raise. Finally, the approach presented here is compared with those taken by the designers of earlier systems, such as PLANNER, HEARSAY-11, and PUP6. This is a preprint of a paper to appear at the Second National Conference of the Canadian Society for Computational Studies of Intelligence, Toronto, Canada, July 1978. .break .begin nofill No. of pages: 27 Cost: $ 2.50 %4-------------------------------------------------------------------------------------%1 %3HPP-78-10 BAOBAB, A PARSER FOR A RULE-BASED SYSTEM USING A SEMANTIC GRAMMAR%1 %3Author:%1 Alain Bonnet .end %3Abstract:%1@Until a recent knowledge-gased system is able to learn by itself, it must acquire new knowledge and new heuristics from human experts. This is traditionally done with the aid of a computer programmer acting as intermediary. The direct transfer of knowledge from an expert to the system requires a natural-language processor capable of handling a substantial subset of English. The development of such a natural-language processor is a long-term goal of automating knowledge acquisition; facilitating the interface between the expert and the system is a first step toward this goal. This paper describes BAOBAB, a program designed and implemented for MYCIN (Shortliffe 1974), a medical consultation system for infectious disease diagnosis and thereapy selection. BAOBAB is concerned with the problem of parsing - recognizing natural language sentences and encoding them into MYCIN's internal representation. For this purpose, it uses a semantic grammar in which the non-terminal symbols denote semantic categories (e.g., infections and symptons), or conceptual catagories which are common tools of knowledge representation in artificial intelligence (e.g., attributes, objects, values and predicate functions). This differs from a syntactic grammar in which non-terminal symbols are syntactic elements such as nouns or verbs. .break .begin nofill No. of pages: 41 Cost: $ 2.85 %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-669 ON THE OPTIMALITY OF LINEAR MERGE%1 %3Authors:%1 Paul K. Stockmeyer & F. Frances Yao .end %3Abstract:%1@Let M(m,n) be the minimum number of pairwise comparisons which will always suffice to merge two linearly ordered lists of lengths m and n . We prove that M(m,m+d) = 2m+d-1 whenever m %2≥%1 2d-2. This generalizes earlier results of Graham and Karp (d = 1), Hwang and Lin (d = 2,3), Knuth (d = 4), and shows that the standard linear merging algorithm is optimal whenever m %2≤%1 n %2≤%1 %5k%13m/2%5l%1+1. .break .begin nofill No. of pages: 11 Cost: $ 2.05 %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-670 INFORMATION BOUNDS ARE WEAK IN THE SHORTEST DISTANCE PROBLEM%1 %3Authors:%1 Ronald L. Graham, Andrew C. Yao, & F. Frances Yao .end %3Abstract:%1@In the all-pair shortest distance problem, one computes the matrix D = (d%9ij%1) where d%9ij%1 is the minimum weighted length of any path from vertex i to vertex j in a directed complete graph with a weight on each edge. In all the known algorithms, a shortest path p%9ij%1 achieving d%9ij%1 is also implicitly computed. In fact, log%93%1f(n) is an information-theoretic lower bound where f(n) is the total number of distinct %2patterns%1 (p%9ij%1) for n-vertex graphs. As f(n) potentially can be as large as 2%6n%63%1, it is hopeful that a non-trivial lower bound can be derived this way in the decision three model. We study the characterization and enumeration of relizable patterns, and show that f(n)#%2≤%1#C∩[n∩[2]] . Thus no lower bound greater than Cn%62%1 can be derived from this approach. We prove as a corollary that the Triangular polyhedron T%6(n)%1 , defined in E%6(##)%1 by d%9ij%2 ≥%1 0 and the triangle inequalities d%9ij%1+d%9jk%2 ≥%1 d%9ik%1 , has at most C∩[n∩[2]] faces of all dimensions, thus resolving an open question in a similar information bound approach to the shortest distance problem. .break .begin nofill No. of pages: 39 Cost: $ 2.80 %4-------------------------------------------------------------------------------------%1 .next page .begin nofill; select 4 .once center SEPTEMBER REPORT ORDER FORM To order reports, or to change your mailing address, return this sheet by: September 8, 1978. .once center Check the reports you wish to receive. HARDCOPY MICROFICHE 1. _____ STAN-CS-78-661 $ 2.35 2. _____ STAN-CS-78-661 FREE 3. _____ STAN-CS-78-662 $ 3.10 4. _____ STAN-CS-78-662 FREE 5. _____ STAN-CS-78-663 $ 2.55 6. _____ STAN-CS-78-663 FREE 7. _____ STAN-CS-78-664 $ 2.20 8. _____ STAN-CS-78-664 FREE 9. _____ STAN-CS-78-665 $ 2.80 A. _____ STAN-CS-78-665 FREE B. _____ STAN-CS-78-666 $ 2.50 C. _____ STAN-CS-78-666 FREE D. _____ HPP-78-7 $ 2.50 E. _____ HPP-78-7 FREE F. _____ HPP-78-10 $ 2.85 G. _____ HPP-78-10 FREE H. _____ STAN-CS-78-669 $ 2.05 I. _____ STAN-CS-78-669 FREE J. _____ STAN-CS-78-670 $ 2.80 K. _____ STAN-CS-78-670 FREE Please do not send money with your order, wait until you get an invoice. _____ Check here to change your address; print changes above the mailing label. ------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------- AFFIX POSTAGE STANFORD UNIVERSITY COMPUTER SCIENCE DEPARTMENT POLYA HALL, ROOM 202 STANFORD, CALIFORNIA 94305 U.S.A. .end