perm filename TEN.PUB[BIB,CSR] blob sn#547112 filedate 1980-11-25 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00011 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .require "setup.csr[bib,csr]" source file C00004 00003 %3STAN-CS-80-822: C00007 00004 %3STAN-CS-80-823: C00009 00005 %3STAN-CS-80-824: C00011 00006 %3STAN-CS-80-825: C00013 00007 %3STAN-CS-80-826: C00015 00008 %3STAN-CS-80-827: C00016 00009 %3STAN-CS-80-828: C00018 00010 %3STAN-CS-80-829: C00020 00011 %3STAN-CS-80-830: C00023 ENDMK C⊗; .require "setup.csr[bib,csr]" source file; .once center %3Stanford University Computer Science Reports%1 List Number 10↔December 1980 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 ''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. -↔- %3STAN-CS-80-822: %2Efficient Algorithms for certain Satisfiability and Linear Programming Problems%1 by Bengt Aspvall (Thesis, 59 pages, September 1980) We present efficient algorithms for certain cases of Linear Equations solving, Linear Programming, and SATisfiability testing. LE, LP, and SAT have all been studied in both the theoretical and the applied areas of Computer Science. Although many algorithms have been developed for these problems, there are large gaps between today's best algorithms and the best theoretical lower bounds. We do not eliminate these gaps, but instead present efficient algorithms for LE, LP, and SAT (and for testing the truth of Quantified Boolean Formulas) for the cases in which there are at most two variables or literals per equation, inequality, or clause. These subcases seem to be the ''hardest'' ones that are not as hard as the general problems. The algorithms for LE(2), 2-SAT, and 2-QBF are linear-time algorithms, and they are optimal except for constant factors. Our algorithm for the subcase of LP has a nonlinear worst-case bound, but the bound is better than for any general LP algorithm such as the polynomial-time algorithm by Khachiyan, and the algorithm seems to be of practical as well as theoretical importance. In the algorithms, we associate graphs with given problem instances. By performing searches on the graphs (in the LP case combined with a binary search technique), we construct a solution or a satisfying truth assignment if one exists. We present also a linear-time algorithm, which uses the 2-SAT algorithm, for mapping certain Boolean expressions in Conjunction Normal Form to equivalent CNF expressions having at most one negated variable per clause (without increasing the length of the expression); such CNF expressions can be tested for satisfiability in linear time. -↔- %3STAN-CS-80-823: %2Knowledge-Based Retrieval on a Relational Database Machine%1 by David Elliot Shaw (Thesis, 280 pages, August 1980) The central focus of this research has been the efficient retrieval of records from very large databases in applications where the criteria for description-matching require deductive inference over a domain-specific ''knowledge base''. Our approach has involved the design of a specialized non-von Neumann machine which permits the highly efficient evaluation of certain operators of a %2relational algebra%1 of particular importance to the computational task of logical satisfaction. The architecture permits an %2O(log n)%1 improvement over the best known evaluation methods for these operators on a conventional computer system, and may also offer a significant improvement over the performance of previously implemented or proposed database machines in other applications of practical import. -↔- %3STAN-CS-80-824: %2LCCD, A Language for Chinese Character Design%1 by Tung Yun Mei (63 pages, October 1980) LCCD is a computer system able to produce aesthetically pleasing Chinese characters for use on raster-oriented printing devices. It is analogous to METAFONT, in that the user writes a little program that explains how to draw each character; but it uses different types of simulated 'pens' that are more appropriate to the Chinese idiom, and it includes special scaling features so that a complex character can easily be built up from simpler ones, in an interactive manner. This report contains a user's manual for LCCD, together with many illustrative examples and a discussion of the algorithms used. -↔- %3STAN-CS-80-825: %2Refined Analysis and Improvements on Some Factoring Algorithms%1 by C. P. Schnorr (30 pages, November 1980) By combining the principles of known factoring algorithms we obtain some imporved algorithms which by heuristic arguments all have time bound %2O(exp %4\%2c ln n ln ln n)%2 for various constants %2c ≥ 3%1. In particular, Miller's method of solvin index equations and Shanks method of computing ambiguous quadratic forms with determinant %2-n%1 can be modified in this way. We show how to speed up the factorization of %2n%1 by using preprocessed lists of thos numbers %1α[%2-u, u%1α]%1 and %1α[%2n-u, n+u%1α]%1, %20 << u << n%1 which only have small prime factors. These lists can be uniformly used for the factorization of all numbers in %1α[%2n-u, n+u%1α]%1. Given these lists, factorization takes %2O(exp %1α[%22(ln n)∩[1/3](ln ln n)∩[2/3]%1α]%2)%1 steps. We slightly improve Dixon's rigorous analysis of his Monte Carlo factoring algorithm. We prove that this algorithm with probability %21/2%1 detects a proper factor of every composite %2n%1 within %2O(exp %4\%26 ln n ln ln n)%1 steps. -↔- %3STAN-CS-80-826: %2A Database Approach to Communication in VLSI Design%1 by Gio Wiederhold, Anne Beetem, and Garrett Short (11 pages, October 1980) This paper describes recent and planned work at Stanford in applying database technology to the problems of VLSI design. In particular, it addresses the issue of communication within a design's different representations and hierarchical levels in a multiple designer environment. We demonstrate the heretofore questioned utility of using commercial database systems, at least while developing a versatile, flexible, and generally efficient model and its associated communication paths. Completed work and results from initial work using DEC DBMS-20 is presented, including macro expansion within the database, and signalling of changes to higher structural levels. Considerable discussion regarding overall philosophy for continued work is also included. -↔- %3STAN-CS-80-827: %2On the Parallel Computation for the Knapsack Problem%1 by Andrew Chi-Chih Yao (11 pages, November 1980) We are interested in the complexity of solving the knapsack problem with %2n%1 input real numbers on a parallel computer with real arithmetic and branching operations. A processor-time tradeoff constraint is derived; in particular, it is shown that aa exponential number of processors have to be used if the problem is to be solved in time %2t ≤ %4\%2n/2%1. -↔- %3STAN-CS-80-828: %2Breaking Paragraphs Into Lines%1 by Donald E. Knuth and Michael F. Plass (66 pages, November 1980) This paper discusses a new approach to the problem of dividing the text of a paragraph into lines of approximately equal length. Instead of simply making decisions one line at a time, the method considers the paragraph as a whole, so that the final appearance of a given line might be influenced by the text on succeeding lines. A system based on three simple primitive concepts called 'boxes', 'glue', and 'penalties' provides the ability to deal satisfactorily with a wide variety of typesetting problems in a unified framework, using a single algorithm that determines optimum breakpoints. This algorithm avoids backtracking by a judicious use of the techniques of dynamic programming. Extensive computational experience confirms that the approach is both efficient and effective in producing high-quality output. The paper concludes with a brief history of line-breaking methods, and an appendix presents a simplified algorithm that requires comparatively few resources. -↔- .next page %3STAN-CS-80-829: %2The Dinner Table Problem%1 by Bengt Aspvall and Frank Liang (14 pages, December 1980) This report contains two papers inspired by the "dinner table problem": If %2n%1 people are seated randomly around a circular table for two meals, what is the probability that no two people sit together at both meals? We show that this probability approaches %2e∩[-2]%1 as %2n → %5α∞%1, and also give a closed form. We then observe that in many similar problems on permutations with restricted position, the number of permutations satisfying a given number of properties is approximately Poisson distributed. We generalize our asymptotic argument to prove such a limit theorem, and mention applications to the problems of derangements, menages, and the asymptotic number of Latin rectangles. -↔- %3STAN-CS-80-830: %2Two Linear-Time Algorithms for Five-Coloring a Planar Graph%1 by David W. Matula, Yossi Shiloach and Robert E. Tarjan (23 pages, December 1980) A "sequential processing" algorithm using bicolor interchange that five- colors an %2n%1 vertex planar graph in O(%2n%1↑2) time was given by Matula, Marble, and Isaacson [MMI 72]. Lipton and Miller used a "bach processing" algorithm with bicolor interchange for the same problem and achieved an improved O(%2n%1 log %2n%1)time bound [LM 78]. In this paper we use graph contraction arguments instead of bicolor interchange and improve both the sequential processing and batch processing methods to obtain five-coloring algorithms that operate in O(%2n%1) time. -↔-