@make(PublicationOrderForm,Number 19,AnnouncementDate "November 1982")
@begin(center)
List Number 19
@end(center)
@Entry(Code "STAN-CS-82-924",
	Title "Adaptive Mesh Refinement for Hyperbolic
		Partial Differential Equations",
	Author "Marsha J. Berger",
	Price "$5.70",              
	Mprice "$2.00",
	Note "123 pages",
	Date "August 1982")

This thesis presents a method based on the idea of multiple, component 
grids for the solution of hyperbolic partial differential equatiions (pde)
using explicit finite difference techniques.  Based upon Richardson-type 
estimates of the local truncation error, refined grids are created or    
existing ones removed to attain a given accuracy for a minimum amount of work.  
In addition, this approach is recursive in that fine grids can themselves 
contain even finer subgrids.  Those grids with finer mesh width in space will
also have a smaller mesh width in time, making this a mesh refinement algorithm
in time and space.

@Entry(Code "STAN-CS-82-925",
	Title "Synthesis of Communicating Processes from Temporal   
	       Logic Specifications",          
	Author "Pierre L. Wolper",
	Price "$5.60",
	Mprice "$2.00",
	Note "120 pages",
 	Date "August 1982",)

In this thesis, we develop a more expressive version of the  
Temporal Logic (TL) introduced by Pnueli and apply it to the problem           
of specifying and syntheesizing synchronization code for pograms written 
in the language of Communicating Sequential Processis (CSP) developed by 
Hoare.                                                                 
   
@Entry(Code "STAN-CS-82-926", 
	Title "Principles of Rule-Based Systems",
	Author "Bruce G. Buchanan and Richard O. Duda",     
	Price "$3.75",
	Mprice "$2.00",
	Note "58 pages",
	Date "August l982",)

Rule-based expert systems ar surveyed.  The most important considerations
are representtion and inference.  Rule-based systems make strong assumptiions 
about the representation of knowledge as conditional sentences and about the
control of inference inone of three ways.  The problem of reasoning with
incomplete or inexact information is also discussed, as are several other 
issues regarding the design of expert systems.                      


@Entry(Code "STAN-CS-82-927",
	Title "Combining State Machines and Regular Expressions for",
               Automatic Synthesis
        Author "Gu Guoan and John Hobby",
	Price "$2.50",
	Mprice "$2.00",
	Note "15 pages",
	Date "April 1982")


A new method for font compression is introduced and compared to existing 
methods.  A very compact representation is achieved by using a variant
of McCreight's string matching algorithm to compress the bounding
contour.  Results from an actual implementation are given showing the
improvement over other methods and how this varies with resolution
and character complexity.  Compression ratios of up to 150
are achieved for Chinese characters.


@Entry(Code "STAN-CS-82-915",
	Title "Verification of Concurrent Programs;  Proving
        Eventualities by Well-Founded Ranking",
        Author "Zohar Manna and A. Pnueli",
	Price "$2.75",
	Mprice "$2.00",
	Note "25 pages",
	Date "June 1982")

In this paper, one of a series on verification of concurrent programs,
we present proof methods for establishing eventuality and until properties.
The methods are based on well-founded ranking and are applicable to both
just and fair computations.  These methods do not assume a decrease of the
rank at each computation step.  It is sufficient that there exists one process
which decreases the rank when activated.  Fairness then ensures that the program
will eventually attain its goal.

In the finite state case the proofs can be represented by diagrams.  Several
examples are given.


@Entry(Code "STAN-CS-82-916",
	Title "Dynamic Weighted Data Structures",
	Author "Samuel W. Bent",
	Price "$4.40",
	Mprice "$2.00",
	Note "80 pages",
	Date "June 1982")

This thesis discusses implementations of an abstract data structure called
a dynamic dictionary.  Such a data structure stores a collection of items,
each of which is equipped with a key and a weight.  Among the operations
we might wish to perform on such a collection are: (a) accessing an item,
given its key, (b) inserting a new item, (c) deleting an item, (d) joining
two collections into one, (e) splitting a collection into two, (f)
changing the weight of an item. Operations (b)-(f) provide the dynamic
nature of the data structure.

In addition we want the implementation to respect the weights, so that 
accessing a heavy item is quicker than accessing a light one.  In an
optimal binary tree, the path length to an item of weight w in a collection
of total weight W is proportional to log(W/w).  By relaxing the optimality
constraint and considering different kinds of trees, it is possible to retain
this logarithmic access time (with a larger constant factor), and 
simultaneously achieve similar logarithmic times for the dynamic operations.

@Entry(Code "STAN-CS-82-917",
	Title "Motion Sequencing of Manipulators",
	Author "Mohamed Shahid Mujtaba",
	Price "$11.20",
	Mprice "not available",
	Note "307 pages",
	Date "July 1982")

Programming of mechanical manipulators or robots is currently either by guiding
or by specifying arm motion symbolically in a programming language.  Guiding
is suitable when the arm goes through the same sequence of operations 
repeatedly; it is unsuitable for making decisions, programming actions based
on real-time sensory data, or concurrent action.  Programming languages 
overcome some of these limitations; however, they require detailed 
instructions for performing even the simplest tasks in assembling parts, and
the user requires special training to program the arm.  Manipulators will be
used extensively for industrial assembly in the future.  Therefore, some means
to simplify manipulator programming is needed.

Experience in using manipulators was gained by programming the assembly
of flashlights, lawn sprinklers and other objects using AL, an
interactive programming language for robots at the Stanford Artificial
Intelligence Laboratory.  Analysis of the programs disclosed commonly 
repeated sequences of operations.

@Entry(Code "STAN-CS-82-918",
	Title "Planning Natural-Language Utterances to Satisfy Multiple Goals",
	Author "Douglas E. Appelt",
	Price "not available",
	Mprice "$2.00",
	Note "188 pages",
	Date "December 1981")

This dissertation presents the results of research on planning formalism for a
theory of natural-language generation that will support the generation of 
utterances that satisfy multiple goals.  Previous research in the area of 
computer generation of natural-language utterances has concentrated two
aspects of language production:  (1) the process of producing surface
syntactic forms from an underlying representation, and (2) the planning
of illocutionary acts to satisfy the speaker's goals.  This work 
concentrates on the interaction between these two aspects of language generation
and considers the overall problem to be one of refining the specification
of an illocutionary act into a surface syntactic form, emphasizing the
problems of achieving multiple goals in a single utterance.

@Entry(Code "STAN-CS-82-920",
	Title "Evaluation of Computer Text Editors",
	Author "Teresa L. Roberts",
	Price "not available",
	Mprice "$2.00",
	Note "188 pages",
	Date "November 1979")

This thesis explores the possiblity of performing an objective and thorough, but
quick, evaluation of text editors from the viewpoints of their various
users.  The methodology presented here covers four general areas of text
editor use: (1) speed at which normal text modification can be done is
measured by observing experienced users as they perform such tasks.  An analytic
model is used to predict this speed from the keystrokes the user has to type
to perform the tasks.  (2)  Ease of learning to perform basic text modifications
is tested by teaching novices to perform those tasks.  An attempt is made
to predict the results of these experiments from the command language 
specification.  (3) The range of functionality available in the editor is
tested by a checklist, and ease of use of this power is evaluated by a 
questionnaire given to the experienced users.  (4)  Finally, how error-prone
the editor is, is tested by recording the amount of time the experienced users
spend in the speed experiments making and correcting errors, by putting stress
on the expert users while they perform simple tasks, and by checking the command
language for its protection of the user from disastrous errors.

@Entry(Code "STAN-CS-82-921",
	Title "Kinematic and Force Analysis of Articulated Hands",
	Author "J. Kenneth Salisbury, Jr.",
	Price "$5.20",
	Mprice "not available",
	Note "106 pages",
	Date "July 1982")

As the application of mechanical manipulators has grown in the fields of 
industrial automation, prosthetics and remote manipulation, the need for
more versatile and adaptable end effectors has become increasingly apparent.
Current manipulation practice is severely limited by our inability to adapt
to a variety of parts and the lack of fidelity in force control.  It has 
become clear that articulated end effectors, or mechanical hands, can be used
to extend manipulation capability in terms of cost effectiveness and in terms
of the overall complexity of tasks that may be performed.  Coupled with
more intelligent control systems, articulated hands promise to be of major
importance in the future of robotics.

@Entry(Code "STAN-CS-82-922",
	Title "An Approach to Verifying Completeness and Consistency in a
	       Rule-Based Expert System",
	Author "Suwa, Scott, and Shortliffe",
	Price "$2.80",
	Mprice "$2.00",
	Note "26 pages",
	Date "June 1982")

We describe a program for verifying that a set of rules in an expert system
comprehensively spans the knowledge of a specialized domain.  The program
has been devised and tested within the context of the ONCOCIN System, a
rule-based consultant for clinical oncology.  The stylized format of
ONCOCIN's rules has allowed the automatic detection of a number of common
errors as the knowledge base has been developed.  This capability
suggests a general mechanism for correcting many problems with knowledge
base completeness and consistency before they can cause performance errors.

@Entry(Code "STAN-CS-82-923",
	Title "Explanatory Power for Medical Expert systems:  Studies in the
	       Representation of Causal Relationships for Clinical 
	       Consultations",
	Author "Jerold W. Wallis and Edward H. Shortliffe",
	Price "$3.30",
	Mprice "$2.00",
	Note "44 pages",
	Date "July 1982")

This paper reports on experiments designed to identify and implement 
mechanisms for enhancing the explanation capabilities of reasoning programs for
medical consultation.  The goals of an explanation system are discussed, as
is the additional knowledge needed to meet these goals in a medical domain.  We
have focused on the generation of explanations that are appropriate for
different types of system users.  This task requires a knowledge of what is
complex and what is important; it is further strengthened by a classification
of the associations or causal mechanisms inherent in the inference rules.  A
causal representation can also be used to aid in refining a comprehensive
knowledge base so that the reasoning and explanations are more adequate. 
accescribe a prototype system which reasons from causal inference rules and
generates explanations that are appropriate for the user.

@send(order <@b{@\Sub-totals@\@Ux(@hsp(.5 inch))@\@Ux(@hsp(.5 inch))}>)
@send(order <@b{@\Publications total@\@Ux(@hsp(.5 inch))}>)
@send(order <@b{@\Sales tax@\@Ux(@hsp(.5 inch))}>)
@send(order <@b{@\Total enclosed@\@Ux(@hsp(.5 inch))}>)