perm filename SIX[BIB,CSR] blob
sn#484141 filedate 1979-10-23 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00016 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 .require "setup.abs[bib,csr]" source file
C00004 00003 .begin center
C00007 00004 .begin nofill <<CS-760>>
C00009 00005 .begin nofill <<CS-761>>
C00010 00006 .begin nofill <<CS-762>>
C00011 00007 .begin nofill <<CS-763>>
C00012 00008 .begin nofill <<CS-764>>
C00013 00009 .begin nofill <<CS-765>>
C00014 00010 .begin nofill <<CS-766>>
C00016 00011 .begin nofill <<CS-767>>
C00017 00012 .begin nofill <<CS-768>>
C00019 00013 .begin nofill <<CS-769>>
C00025 00014 .begin nofill <<CS-770>>
C00027 00015 .begin nofill <<cs-771>>
C00032 00016 .select 4 <<order form>>
C00035 ENDMK
C⊗;
.require "setup.abs[bib,csr]" source file;
.font A "math40";
.font B "math50";
.at "⊗" ⊂"%5αQ%*"⊃
.begin center
S T A N F O R D U N I V E R S I T Y
MOST RECENT COMPUTER SCIENCE REPORTS - 1979
.end
No. 6↔October
@Listed here are abstracts of the most recent reports published by the
Department of Computer Science at 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
December 28, 1979. In many cases we can print only a limited number of copies,
and requests will be filled on a first come, first served basis. 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. 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 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.
.skip
.begin nofill <<CS-760>>
STAN-CS-79-760
@SOME MONOTONICITY PROPERTIES OF PARTIAL ORDERS
Authors: R. L. Graham, A. C. Yao, and F. F. Yao
21 pages↔Cost: $2.30
.end
@A fundamental quantity which arises in the sorting of %2n%1 numbers
%2a↓1,a↓2,...,a↓n%1 is %2Pr(a↓i#<#a↓j#|#P)%1, the probability that
%2a↓i#<#a↓j%1 assuming that all linear extensions of the partial order
%2P%1 are equally likely. In this paper we establish various properties
of %2Pr(a↓i#<#a↓j#|#P)%1 and related quantities. In particular, it is
shown that %2Pr(a↓i#<#b↓j#|#P')#≥#Pr(a↓i#<#b↓j#|#P)%1, if the partial
order %2P%1 consists of two disjoint linearly ordered sets
%2A#=#{a↓1#<#a↓2#<#...#<#a↓m} , B#=#{b↓1#<#b↓2#<#...#<#b↓n}%1 and
%2P'#=#Pα∪{%1any relations of the form %2a↓k#<#b↓l}%1. The inequalities
have applications in determining the complexity of certain sorting-like
computations.
.skip
.begin nofill <<CS-761>>
STAN-CS-79-761
@GOSSIPING WITHOUT DUPLICATE TRANSMISSIONS
Author: Douglas B. West
7 pages↔Cost: $1.90
.end
@%2n%1 people have distinct bits of information, which they communicate via
telephone calls in which they transmit everything they know. We require that
no one ever hear the same piece of information twice. In the case %24%1 divides
%2n, n#≥#8%1, we provide a construction that transmits all information using
only %29n/4-6%1 calls. Previous constructions used !! _;%2n log n%1 calls.
.next page
.begin nofill <<CS-762>>
STAN-CS-79-762
@METAFONT: A System for Alphabet Design
Author: Donald E. Knuth
107 pages↔Cost: $4.70
.end
@This is the user's manual for METAFONT, a companion to the TEX typesetting
system. The system makes it fairly easy to define high quality fonts of
type in a machine-independent manner; a user writes "programs" in a new
language developed for this purpose. By varying parameters of a design, an
unlimited number of typefaces can be obtained from a single set of programs.
The manual also sketches the algorithms used by the system to draw the
character shapes.
.skip
.begin nofill <<CS-763>>
STAN-CS-79-763
@A SYMMETRIC CHAIN DECOMPOSITION OF %2L(4,n)%1
Author: Douglas B. West
17 pages↔Cost: $2.20
.end
@%2L(m,n)%1 is the set of integer %2m%1-tuples %2(a↓1,...,a↓m)%1 with
%20#≤#a↓1#≤#...#≤#a↓m#≤#n%1, ordered by %2a#≤#b%1 when %2a↓i#≤#b↓i%1
for all %2i%1. R. Stanley conjectured that %2L(m,n)%1 is a symmetric chain
order for all %2(m,n)%1. We verify this by construction for %2m#=#4%1.
.skip
.begin nofill <<CS-764>>
STAN-CS-79-764
@ON THE TIME-SPACE TRADEOFF FOR SORTING WITH LINEAR QUERIES
Author: Andrew Chi-Chih Yao
33 pages↔Cost: $2.65
.end
@Extending a result of Borodin, et. al. [1], we show that any branching
program using linear queries "#%A$%5l%2↓ix↓i#:#c%1#" to sort %2n%1 numbers
%2x↓1,x↓2,...,x↓n%1 must satisfy the time-space tradeoff relation
%2TS#=#%5W%2(n↑2)%1. The same relation is also shown to be true for
branching programs that uses queries "#%2min#R#=#?%1#" where %2R%1 is
any subset of %2{x↓1,x↓2,...,x↓n}%1.
.skip
.begin nofill <<CS-765>>
STAN-CS-79-765
@RELATION BETWEEN THE COMPLEXITY AND THE PROBABILITY OF LARGE NUMBERS
Author: Peter Gacs
8 pages↔Cost: $1.95
.end
@%2H(x)%1, the negative logarithm of the apriori probability %2M(x)%1,
is Levin's variant of Kolmogorov's complexity of a natural number %2x%1.
Let %2αα(n)%1 be the minimum complexity of a number larger than %2n%1,
%2s(n)%1 the logarithm of the apriori probability of obtaining a
number larger than %2n%1. It was known that
.skip
.once center
%2s(n)#≤#αα(n)#≤#s(n)#+#H(%3k%2s(n)%3l%2)%1#.
We show that the second estimate is in some sense sharp.
.next page
.begin nofill <<CS-766>>
STAN-CS-79-766↔(SU326 P3069)
@EQUIDISTRIBUTING MESHES WITH CONSTRAINTS
Authors: J. Kautsky and N. K. Nichols
27 pages↔Available in microfiche only.
.end
@Adaptive methods for selecting meshes which "equi-distribute" a given
positive weight function are now used fairly widely in solving
boundary value problems. The disadvantage of such schemes is that
the resulting mesh may not be smoothly varying, which adversely
affects accuracy and convergence properties. In this paper an adaptive
technique is developed for equidistributing a function subject to
constraints on the ratios of %2adjacent%1 steps in the mesh. Given a
weight function %2f ≥ 0%1 on interval %2[a,b]%1 and constants %2c%1 and %2K%1,
the method produces a mesh with points %2x↓0#=#a, x∪[j+1]#=#x↓j#+#h↓j,
j#=#0,1,..#n-1%1 and %2x↓n#=#b%1 such that
.skip
.begin bf
.tabs 15,20
\%2x∪[j+1]
\%BI%2\f ≤ c%1 and %2l/K ≤ h∪[j+1]/h↓j ≤ K%1 for %2j = 0,1,..n-1
\x↓j%1
.end
A theoretical analysis of the procedure is presented, and numerical
algorithms for implementing the method are given. Applications show
that the procedure is effective in practice. Other types of constraints
on equidistributing meshes are also discussed.
.skip
.begin nofill <<CS-767>>
STAN-CS-79-767
@ON STEWART'S SINGULAR VALUE DECOMPOSITION FOR PARTITIONED ORTHOGONAL
@MATRICES
Author: Charles Van Loan
17 pages↔Available in microfiche only.
.end
A variant of the singular value decomposition for orthogonal matrices due
to G. W. Stewart is discussed. It is shown to be useful in the analysis
of (a) the total least squares problem, (b) the Golub-Klema-Stewart subset
selection algorithm, and (c) the algebraic Riccati equation.
.skip
.begin nofill <<CS-768>>
STAN-CS-79-768
@CAUSAL NETWORKS or What Is a Deterministic Computation?
Authors: Peter Gacs and Leonid A. Levin
24 pages↔Cost: $2.40
.end
@We introduce the concept of casual networks which can be considered as
the most general concept of the record of a computation (sequential or
parallel). Causality and locality are distinguished as the only important
properties of networks representing such records. Different types of
complexities of computations correspond to different geometrical characteristics
of the corresponding causal networks which have the advantage of being finite
objects. Synchronity becomes a relative notion. Our networks can be
symmetric therefore the question will make sense what can be computed from
arbitrary symmetric inputs. Here we obtain a complete group-theoretical
characterisation of the kind of symmetrics that can be allowed in parallel
computations.
.next page
.begin nofill <<CS-769>>
STAN-CS-79-769
@TRANSFER OF RULE-BASED EXPERTISE THROUGH A TUTORIAL DIALOGUE
Author: William John Clancey↔(Thesis)
462 pages↔Available in microfiche only.
.end
@This dissertation describes an intelligent, computer-aided instructional (ICAI)
program, named GUIDON, with capabilities to carry on a structured case method
dialogue, generate teaching material from production rules, construct and verify
a model of what the student knows, and explain expert reasoning. The principle
objective of this research has been to convert MYCIN, a knowledge-based consultation
program, into an effective instructional tool. GUIDON combines the subject matter
knowledge of the consultation system with tutorial discourse knowledge, while
keeping the two distinct.
@MYCIN-like knowledge-based consultation programs are designed to provide
expert-level advise about difficult scientific and medical problems. High
performance is attained by interpreting a large, specialized set of facts and
domain relations that take the form of rules about what to do in a given
circumstance. Such a rule base is generally built by interviewing human experts
to formulate the knowledge that they use to solve similar problems in their area
of expertise. While it is generally believed that these programs have significant
educational potential, little work has been done to evaluate the problems of
realizing this potential.
@Using a rule base for teaching provides a new perspective for showing what
production rules have to do with human expertise. This dissertation closely
examines the usefulness and adequacy of MYCIN's rules for infectious disease
diagnosis as an instructional vehicle: as topics to be discussed in a tutorial,
as problem-solving methods for understanding a student's behavior, and as skills
to be learned by a student. It is argued that MYCIN-like rule-bases systems
constitute a good starting point for developing a tutorial program, but they are
not sufficient in themselves for making knowledge accessible to a student. Using
GUIDON as an interactive medium for transferring expertise provides a larger
context about human cognition; this is reflected in our consideration of subject
matter representation and principles of tutorial discourse.
@The study of subject matter representation focuses on knowledge that allows the
tutor to articulate the structure, underlying principles, and strategies of the
domain. This dissertation pays particular attention to aspects of human expertise
that have not been captured by the MYCIN rule base, a kind of investigation that
has not arisen in the construction, maintenance, and use of this knowledge base
for consultation.
@The study of tutorial discourse principles focuses on managing the dialogue to
achieve economical, systematic presentation of problem-solving expertise. In
addition, tutoring methods for opportunistically presenting new material and
providing hints on the basis of an hypothesis revision strategy are demonstrated.
GUIDON's teaching and discourse expertise is represented as explicit rules.
These rules comprise strategies for modeling the student, means for sharing
initiative, and knowledge of conventional procedures for discussing a problem
in a "goal-directed" way.
@After the basic set of tutorial expertise was developed using MYCIN's
infectious disease rule set, some perspective on GUIDON's generality and domain
independence was attained by coupling it to rule sets for other domains, including
an engineering application. Two experiments of this type were performed. They
reveal the relationship of discourse strategies to the reasoning structure of
the problem being discussed.
.skip
.begin nofill <<CS-770>>
STAN-CS-79-770↔(PVG-13)
@PRETTY PRINTING
Author: Derek C. Oppen
20 pages↔Cost: $2.30
.end
@An algorithm for pretty printing is given. For an input stream of
length %2n%1 and an output device with margin width %2m%1, the algorithm requires
time %2O(n)%1 and space %2O(m)%1. The algorithm is described in terms of two
parallel processes; the first scans the input stream to determine the
space required to print logical blocks of tokens; the second uses this
information to decide where to break lines of text; the two processes
communicate by means of a buffer of size %2O(m)%1. The algorithm does not
wait for the entire stream to be input, but begins printing as soon as it
has received a linefull of input. The algorithm is easily implemented.
.skip
.begin nofill <<cs-771>>
STAN-CS-79-771
@KNOWLEDGE-BASED EXPERIMENT DESIGN IN MOLECULAR GENETICS
Author Peter E. Friedland↔(Thesis)
137 pages↔Available in microfiche only.
.end
@Laboratory science includes both a design and an implementation stage. Before
a competent experimentalist commits his time and resources to achieving some
goal, he produces a working outline of the experiment, a guide to each step of
the process. The purpose of this work -- MOLGEN -- is to examine and model this
design process for the domain of molecular genetics with the aim of producing
a tool of significant utility to the laboratory scientist.
@The work may be viewed in two perspectives within the domain of artificial
intelligence. First, it is a substantial experiment in knowledge engineering
with a real system. The experiment design system encompasses problems of
knowledge representation and acquisition, as well as research into using that
knowledge effectively within a hierarchial planning system. Second, the work
has a strong cognitive science aspect. An informal study of human scientists
was made with the aim of developing a theory of human performance in a complex
scientific task, and then implementing this theory in an automated experiment
design system.
@The research described in this thesis consits of five major parts: work
toward a theory of how scientists design experiments, construction of a system
for knowledge-base acquisition, building an expert knowledge-base for a large
part of the domain, implementing the theory of human performance in a manner
whichmakes efficient use of that knowledge base, and testing the system on real
problems in molecular genetics. Individual chapters detail each of the parts,
and also provide an annotated example of the design system at work and a
description of current problems and future research
@The design system is based on the observation that scientists rarely invent an
experiment design from scratch. Usually they begin with an abstract or
"skeletal" plan which contains the basic steps, which, if successfully carried
out, will provide a solution for the experimental goal. The major design task
is to instantiate each of the plan-steps with a method which will actually work
within the environment of the particular problem. The skeletal plans range
from general to specific, depending upon the experimenter and the problem.
@The experiment design system is currently (June 1979) operational on a variety
of design problems in molecular genetics. It has been most successful, i.e. it
produces plausible experimental plans, for analytical problems where the goal
is to elucidate structural features of nucleic acid molecules. The knowledge
base, build by expert molecular biologists, contains declarative and procedural
information about structures, laboratory conditions, laboratory techniques
which modify, separate, and detect structural features, and abstract experimental
plans for structural analysis.
.next page
.select 4 <<order form>>
REPORT ORDER FORM α#6↔Order Deadline: December 28, 1979
To order reports, or to change your mailing address, complete and return the ENTIRE
form (including the mailing label) to: Publications Coordinator, Department of
Computer Science, Stanford University, Stanford, California 94305, U.S.A.
.skip
.begin nofill
Hardcopy Microfiche
1._____ STAN-CS-79-760 $2.30 2._____ STAN-CS-79-760 FREE
3._____ STAN-CS-79-761 $1.90 4._____ STAN-CS-79-761 FREE
5._____ AIM-332 $4.70 6._____ AIM-332 FREE
7._____ STAN-CS-79-763 $2.20 8._____ STAN-CS-79-763 FREE
9._____ STAN-CS-79-764 $2.65 A._____ STAN-CS-79-764 FREE
B._____ STAN-CS-79-765 $1.95 C._____ STAN-CS-79-765 FREE
E._____ STAN-CS-79-766 FREE
G._____ STAN-CS-79-767 FREE
H._____ STAN-CS-79-768 $2.40 I._____ STAN-CS-79-768 FREE
K._____ STAN-CS-79-769 FREE
L._____ STAN-CS-79-770 $2.30 M._____ STAN-CS-79-770 FREE
O._____ STAN-CS-79-771 FREE
.end
%4Please do NOT send money with your order. Wait until you receive an invoice,
which is enclosed with the reports when they're sent.
.skip
.begin indent 0,8,0
_____ Check here to change your address. Print the changes above the
mailing label, and return this ENTIRE form (including the mailing
label) to: Publications Coordinator, Department of Computer Science,
Stanford University.
.end
.skip 10
.begin nofill
%4Stanford University
Department of Computer Science
Stanford, California 94305
.end