/LMAR=0/XLINE=10/FONT#0=NONM/FONT#1=BAXM30/FONT#2=MATH30/FONT#3=SAIL25/FONT#4=GRKL30/FONT#5=ZERO30/FONT#9=MATH40/FONT#10=MATH50
␈↓ α∧␈↓␈↓ ¬∞S T A N F O R D   U N I V E R S I T Y
␈↓"β␈↓ α∧␈↓␈↓ ∧⊗MOST RECENT COMPUTER SCIENCE REPORTS - 1979

␈↓"β␈↓ α∧␈↓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.

␈↓"β␈↓ α∧␈↓STAN-CS-79-760
␈↓"β␈↓ α∧␈↓    SOME MONOTONICITY PROPERTIES OF PARTIAL ORDERS
␈↓"β␈↓ α∧␈↓Authors:  R. L. Graham, A. C. Yao, and F. F. Yao
␈↓"β␈↓ α∧␈↓21 pages␈↓ 
RCost:  $2.30

␈↓"β␈↓ α∧␈↓    A␈α∃fundamental␈α∀quantity␈α∃which␈α∀arises␈α∃in␈α∃the␈α∀sorting␈α∃of␈α∀␈↓↓n␈↓␈α∃numbers␈α∃␈↓↓a␈↓#v1␈↓#,a␈↓#v2␈↓#,...,a␈↓#vn␈↓#␈↓␈α∀is
␈↓ α∧␈↓␈↓↓Pr(a␈↓#vi␈↓# < a␈↓#vj␈↓# | P)␈↓,␈α
the␈α
probability␈αthat␈α
␈↓↓a␈↓#vi␈↓# < a␈↓#vj␈↓#␈↓␈α
assuming␈αthat␈α
all␈α
linear␈αextensions␈α
of␈α
the␈αpartial
␈↓ α∧␈↓order␈α
␈↓↓P␈↓␈α
are␈α∞equally␈α
likely.␈α
 In␈α∞this␈α
paper␈α
we␈α∞establish␈α
various␈α
properties␈α∞of␈α
␈↓↓Pr(a␈↓#vi␈↓# < a␈↓#vj␈↓# | P)␈↓
␈↓ α∧␈↓and␈α
related␈α
quantities.␈α
 In␈α
particular,␈α
it␈α
is␈α
shown␈α
that␈α
␈↓↓Pr(a␈↓#vi␈↓# < b␈↓#vj␈↓# | P') ≥ Pr(a␈↓#vi␈↓# < b␈↓#vj␈↓# | P)␈↓,␈α
if␈α
the
␈↓ α∧␈↓partial␈α∩order␈α⊃␈↓↓P␈↓␈α∩consists␈α⊃of␈α∩two␈α⊃disjoint␈α∩linearly␈α⊃ordered␈α∩sets␈α∩␈↓↓A = {a␈↓#v1␈↓# < a␈↓#v2␈↓# < ... < a␈↓#vm␈↓#}␈α⊃,
␈↓ α∧␈↓↓B = {b␈↓#v1␈↓# < b␈↓#v2␈↓# < ... < b␈↓#vn␈↓#}␈↓␈αand␈α␈↓↓P' = P∪{␈↓any␈α
relations␈αof␈αthe␈α
form␈α␈↓↓a␈↓#vk␈↓# < b␈↓#vl␈↓#}␈↓.␈α The␈αinequalities␈α
have
␈↓ α∧␈↓applications in determining the complexity of certain sorting-like computations.

␈↓"β␈↓ α∧␈↓STAN-CS-79-761
␈↓"β␈↓ α∧␈↓    GOSSIPING WITHOUT DUPLICATE TRANSMISSIONS
␈↓"β␈↓ α∧␈↓Author:  Douglas B. West
␈↓"β␈↓ α∧␈↓7 pages␈↓ 
RCost:  $1.90

␈↓"β␈↓ α∧␈↓    ␈↓↓n␈↓␈α
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␈α␈↓↓4␈↓␈αdivides␈α␈↓↓n,␈αn ≥ 8␈↓,␈αwe␈αprovide␈αa␈αconstruction␈αthat
␈↓ α∧␈↓transmits␈α∞all␈α∂information␈α∞using␈α∂only␈α∞␈↓↓9n/4-6␈↓␈α∂calls.␈α∞ Previous␈α∂constructions␈α∞used␈α∂ ␈↓#
_␈↓#␈αp␈↓#v␈α∞␈↓#␈α⊂␈↓↓n␈α∂log␈α∞n␈↓
␈↓ α∧␈↓calls.
␈↓ α∧␈↓STAN-CS-79-762
␈↓"β␈↓ α∧␈↓    METAFONT:  A System for Alphabet Design
␈↓"β␈↓ α∧␈↓Author:  Donald E. Knuth
␈↓"β␈↓ α∧␈↓107 pages␈↓ 
RCost:  $4.70

␈↓"β␈↓ α∧␈↓    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.

␈↓"β␈↓ α∧␈↓STAN-CS-79-763
␈↓"β␈↓ α∧␈↓    A SYMMETRIC CHAIN DECOMPOSITION OF ␈↓↓L(4,n)␈↓
␈↓"β␈↓ α∧␈↓Author:  Douglas B. West
␈↓"β␈↓ α∧␈↓17 pages␈↓ 
RCost:  $2.20

␈↓"β␈↓ α∧␈↓    ␈↓↓L(m,n)␈↓␈αis␈αthe␈αset␈αof␈αinteger␈α␈↓↓m␈↓-tuples␈α␈↓↓(a␈↓#v1␈↓#,...,a␈↓#vm␈↓#)␈↓␈αwith␈α␈↓↓0 ␈↓β≤␈↓↓ a␈↓#v1␈↓# ␈↓β≤␈↓↓ ... ␈↓β≤␈↓↓ a␈↓#vm␈↓# ␈↓β≤␈↓↓ n␈↓,␈αordered␈αby
␈↓ α∧␈↓␈↓↓a ␈↓β≤␈↓↓ b␈↓␈αwhen␈α
␈↓↓a␈↓#vi␈↓# ␈↓β≤␈↓↓ b␈↓#vi␈↓#␈↓␈αfor␈α
all␈α␈↓↓i␈↓.␈α
 R.␈αStanley␈α
conjectured␈αthat␈α
␈↓↓L(m,n)␈↓␈αis␈α
a␈αsymmetric␈α
chain␈αorder
␈↓ α∧␈↓for all ␈↓↓(m,n)␈↓.  We verify this by construction for ␈↓↓m = 4␈↓.

␈↓"β␈↓ α∧␈↓STAN-CS-79-764
␈↓"β␈↓ α∧␈↓    ON THE TIME-SPACE TRADEOFF FOR SORTING WITH LINEAR QUERIES
␈↓"β␈↓ α∧␈↓Author:  Andrew Chi-Chih Yao
␈↓"β␈↓ α∧␈↓33 pages␈↓ 
RCost:  $2.65

␈↓"β␈↓ α∧␈↓    Extending␈α∂a␈α∂result␈α∂of␈α∂Borodin,␈α∂et.␈α∂al.␈α∂[1],␈α∂we␈α∂show␈α∂that␈α∂any␈α∂branching␈α∂program␈α∂using
␈↓ α∧␈↓linear␈α⊂queries␈α⊃" ␈↓	$␈↓∧l␈↓↓␈↓#vi␈↓#x␈↓#vi␈↓# : c␈↓ "␈α⊂to␈α⊂sort␈α⊃␈↓↓n␈↓␈α⊂numbers␈α⊂␈↓↓x␈↓#v1␈↓#,x␈↓#v2␈↓#,...,x␈↓#vn␈↓#␈↓␈α⊃must␈α⊂satisfy␈α⊃the␈α⊂time-space
␈↓ α∧␈↓tradeoff␈α⊂relation␈α⊂␈↓↓TS = ␈↓∧W␈↓↓(n␈↓#
2␈↓#)␈↓.␈α⊃ The␈α⊂same␈α⊂relation␈α⊃is␈α⊂also␈α⊂shown␈α⊃to␈α⊂be␈α⊂true␈α⊃for␈α⊂branching
␈↓ α∧␈↓programs that uses queries " ␈↓↓min R = ?␈↓ " where ␈↓↓R␈↓ is any subset of ␈↓↓{x␈↓#v1␈↓#,x␈↓#v2␈↓#,...,x␈↓#vn␈↓#}␈↓.

␈↓"β␈↓ α∧␈↓STAN-CS-79-765
␈↓"β␈↓ α∧␈↓    RELATION BETWEEN THE COMPLEXITY AND THE PROBABILITY OF LARGE NUMBERS
␈↓"β␈↓ α∧␈↓Author:  Peter Gacs
␈↓"β␈↓ α∧␈↓8 pages␈↓ 
RCost:  $1.95

␈↓"β␈↓ α∧␈↓    ␈↓↓H(x)␈↓,␈α⊗the␈α∃negative␈α⊗logarithm␈α∃of␈α⊗the␈α∃apriori␈α⊗probability␈α∃␈↓↓M(x)␈↓,␈α⊗is␈α∃Levin's␈α⊗variant␈α∃of
␈↓ α∧␈↓Kolmogorov's␈α∞complexity␈α∞of␈α∞a␈α∞natural␈α∞number␈α∞␈↓↓x␈↓.␈α
 Let␈α∞␈↓↓α(n)␈↓␈α∞be␈α∞the␈α∞minimum␈α∞complexity␈α∞of␈α
a
␈↓ α∧␈↓number␈α⊂larger␈α⊂than␈α⊂␈↓↓n␈↓,␈α⊂␈↓↓s(n)␈↓␈α⊂the␈α⊂logarithm␈α⊂of␈α⊂the␈α⊂apriori␈α⊂probability␈α⊂of␈α⊂obtaining␈α⊂a␈α∂number
␈↓ α∧␈↓larger than ␈↓↓n␈↓.  It was known that

␈↓"β␈↓ α∧␈↓␈↓ ¬B␈↓↓s(n) ␈↓β≤␈↓↓ α(n) ␈↓β≤␈↓↓ s(n) + H(␈↓αk␈↓↓s(n)␈↓αl␈↓↓)␈↓ .

␈↓"β␈↓ α∧␈↓We show that the second estimate is in some sense sharp.
␈↓ α∧␈↓STAN-CS-79-766␈↓ 
&(SU326 P3069)
␈↓"β␈↓ α∧␈↓    EQUIDISTRIBUTING MESHES WITH CONSTRAINTS
␈↓"β␈↓ α∧␈↓Authors:  J. Kautsky and N. K. Nichols
␈↓"β␈↓ α∧␈↓27 pages␈↓ 	¬Available in microfiche only.

␈↓"β␈↓ α∧␈↓    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␈α∞␈↓↓adjacent␈↓
␈↓ α∧␈↓steps␈αin␈αthe␈αmesh.␈α
 Given␈αa␈αweight␈αfunction␈α
␈↓↓f␈α≥␈α0␈↓␈αon␈αinterval␈α
␈↓↓[a,b]␈↓␈αand␈αconstants␈α␈↓↓c␈↓␈α
and␈α␈↓↓K␈↓,
␈↓ α∧␈↓the␈α∂method␈α∂produces␈α∞a␈α∂mesh␈α∂with␈α∂points␈α∞␈↓↓x␈↓#v0␈↓# = a,␈α∂x␈↓#vj+1␈↓# = x␈↓#vj␈↓# + h␈↓#vj␈↓#,␈α∂j = 0,1,.. n-1␈↓␈α∂and␈α∞␈↓↓x␈↓#vn␈↓# = b␈↓
␈↓ α∧␈↓such that

␈↓"β␈↓ α∧␈↓␈↓ βd␈↓↓x␈↓#vj+1␈↓#
␈↓"β␈↓ α∧␈↓↓␈↓ βd␈↓
I␈↓↓␈↓ ∧4f ␈↓β≤␈↓↓ c␈↓ and ␈↓↓l/K ␈↓β≤␈↓↓ h␈↓#vj+1␈↓#/h␈↓#vj␈↓# ␈↓β≤␈↓↓ K␈↓ for ␈↓↓j = 0,1,..n-1
␈↓"β␈↓ α∧␈↓↓␈↓ βdx␈↓#vj␈↓#␈↓

␈↓"β␈↓ α∧␈↓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.

␈↓"β␈↓ α∧␈↓STAN-CS-79-767
␈↓"β␈↓ α∧␈↓    ON STEWART'S SINGULAR VALUE DECOMPOSITION FOR PARTITIONED ORTHOGONAL
␈↓"β␈↓ α∧␈↓    MATRICES
␈↓"β␈↓ α∧␈↓Author:  Charles Van Loan
␈↓"β␈↓ α∧␈↓17 pages␈↓ 	¬Available in microfiche only.

␈↓"β␈↓ α∧␈↓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.

␈↓"β␈↓ α∧␈↓STAN-CS-79-768
␈↓"β␈↓ α∧␈↓    CAUSAL NETWORKS or What Is a Deterministic Computation?
␈↓"β␈↓ α∧␈↓Authors:  Peter Gacs and Leonid A. Levin
␈↓"β␈↓ α∧␈↓24 pages␈↓ 
RCost:  $2.40

␈↓"β␈↓ α∧␈↓    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.
␈↓ α∧␈↓STAN-CS-79-769
␈↓"β␈↓ α∧␈↓    TRANSFER OF RULE-BASED EXPERTISE THROUGH A TUTORIAL DIALOGUE
␈↓"β␈↓ α∧␈↓Author:  William John Clancey␈↓ ∩(Thesis)
␈↓"β␈↓ α∧␈↓462 pages␈↓ 	¬Available in microfiche only.

␈↓"β␈↓ α∧␈↓    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.

␈↓"β␈↓ α∧␈↓STAN-CS-79-770
␈↓"β␈↓ α∧␈↓    PRETTY PRINTING
␈↓"β␈↓ α∧␈↓Author:  Derek C. Oppen
␈↓"β␈↓ α∧␈↓20 pages␈↓ 
RCost:  $2.30

␈↓"β␈↓ α∧␈↓    An␈αalgorithm␈αfor␈α
pretty␈αprinting␈αis␈αgiven.␈α
 For␈αan␈αinput␈αstream␈α
of␈αlength␈α␈↓↓n␈↓␈αand␈α
an␈αoutput
␈↓ α∧␈↓device␈αwith␈α
margin␈αwidth␈α␈↓↓m␈↓,␈α
the␈αalgorithm␈αrequires␈α
time␈α␈↓↓O(n)␈↓␈αand␈α
space␈α␈↓↓O(m)␈↓.␈α 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␈α∞␈↓↓O(m)␈↓.␈α
 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.
␈↓ α∧␈↓βREPORT ORDER FORM #6␈↓ πSOrder 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.

␈↓"β␈↓ α∧␈↓β           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

␈↓"β␈↓ α∧␈↓βPlease␈α≠do␈α≤NOT␈α≠send␈α≠money␈α≤with␈α≠your␈α≠order.␈α≤ Wait␈α≠until␈α≠you␈α≤receive␈α≠an
␈↓ α∧␈↓βinvoice, which is enclosed with the reports when they're sent.


␈↓"β␈↓ α∧␈↓β_____␈α→ 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.










␈↓"β␈↓ α∧␈↓βStanford University
␈↓"β␈↓ α∧␈↓βDepartment of Computer Science
␈↓"β␈↓ α∧␈↓βStanford, California 94305