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