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.

-↔-