@make(PublicationOrderForm,Number 20,AnnouncementDate "January 1983")
@begin(center)
List Number 20
@end(center)
@Entry(Code "STAN-CS-82-944",
        Title "The WEB System of Structured Documentation",
        Author "Donald E. Knuth",
        Price "$7.90",
        Mprice "$2.00",
        Note "196 pages",
        Date "October 1982")

This memo describes how to write programs in the WEB language; and it also           
includes the full WEB documentation for WEAVE and TANGLE, the programs
that read WEB input and produce TeX and PASCAL output, respectively.  The
philosophy behind WEB is that an experienced system programmer, who wants
to provide the best possible documentation of his or her software
products, needs two things simultaneously:  a language like TeX for
formatting, and a language like PASCAL for programming.  Neither type of 
language can provide the best documentation by itself; but when both are
appropriately combined, we obtain a sustem that is much more useful than
either language separately.

@Entry(Code "STAN-CS-82-945",
	Title "TeXware",
	Author "Donald E. Knuth",
	Price "$5.25",              
	Mprice "$2.00",
	Note "142 pages",
	Date "October 1982")

This report contains four programs that should be helpful to anybody
who is installing the portable version of TeX:  (1) POOLtype list the
contents of a string pool file output by TANGLE; (2) TFtoPL converts
a TeX font metric font metric file to property list format; (3) PLtoTF 
goes the other way, to make font metric files; (4) DVItype lists the 
contents of a device-independent output file and illustrates DVI-reading
programs in general.  All four programs are examples of the WEB
documentation system.


@Entry(Code "STAN-CS-82-946",
	Title "A Test File for TeX,
	Author "Donald E. Knuth",
	Price "$5.90",
	Mprice "$2.00",
	Note "130 pages",
 	Date "October 1982")

Programs that claim to be implementations of TeX82 are supposed to be able
to process the test routine contained in this report, producing the 
outputs contained in this report.  A previously unpublished diagnostic method 
that the author has used successfully for over twenty years is described and
illustrated here.

  
@Entry(Code "STAN-CS-82-947", 
	Title "Modelling Degrees of Item Interest for a General   
              Database Wquery System",
	Author "Neil C. Rowe",     
	Price "$3.10",
	Mprice "$2.00",
	Note "37 pages",
	Date "October l982",)

Many databases support decision-making.  Often this means choices between
alternatives according to partly subjective or conflicting criteria. 
Database query languages are generaally designed for precise, logical
specification of the data of interest, and tent to be awkward in the 
aforementioned circumstances.  Information retrieval research suggests
several solutions, but there are obstacles to generalizing these ideas
to most databases.

To address this problem we propose a methodology fo automatically 
deriving and monitoring "degrees of interest" among alternatives for
a user of a database system.  This includes (a) a decision theory model 
of the value of information to the user, and (b) inference mechanisms, 
based in part on ideas from artificial intelligence, that can tune the 
model to observed user behavior.  This theory has important applications
to improving efficiency and cooperativeness of the interface between a 
decision-maker and a database system.


@Entry(Code "STAN-CS-82-948",
        Title "Three Papers on Rule-Based Estimation of Statistics
               on Databases",
        Author "Neil c. Rowe",
	Price "$3.10",
	Mprice "$2.00",
	Note "38 pages",
	Date "October 1982")

This report contains three papers on rule-based estimation of statistics on
a database:  an overview, followed by two moe specialized papers.  The first,
"Rule-based Statistical Calculations on a Database Abstract," is addressed
to a general database audience, and was presented at the First LBL Workshop 
on Statistical Database Management, Menlo Park, Califoria, December 1981.
The second, "Inheritance of Statistical Properties,," is addressd to an
artificial intelligence audience, and was presented at the National Conference 
of the American Associaiton for Artificial Intelligence, Pittsburgh, 
Pennsylvania, August 1982.  The third, "Diophantine Compromise of a
Statistical Database," is addressed to an audience of database theorists.

@Entry(Code "STAN-CS-82-949",
	Title "The @i[r]-Stirling numbers",
        Author "Andrei Z. Broder",
	Price "$2.70",
	Mprice "$2.00",
	Note "22 pages",
    	Date "November 1982")

The @i[r]-Stirling numbers of the first and second kind count restricted
permutations and respectively restricted partitions, the restrictions being
that the first @i[r] elements must be in distinct cycles and respectively
distinct subsets.  The combinatorial and algebraic properties of these 
numbers, which in most cases generalize similar properties of the regular
Stirling numbers, are explored starting from the above definition.


@Entry(Code "STAN-CS-82-950",
	Title "",
	Author "",
	Price "$",
	Mprice "$2.00",
	Note " pages",
	Date "")












@Entry(Code "STAN-CS-82-951",
	Title "Five Paradigm Shifts in Programming Language Design  
               and Their Realization in Viron, A Dataflow Programmming
               Environment",
	Author "Vaughan Pratt",
	Price "$2.30",
	Mprice "$2.00",
	Note "9 pages",
	Date "July 1982")

We describe five paradigm shifts in programming language design, some old 
and some relatively new, namely Effct to Entity, Serial to Parallel, Partition 
Types to Predicate Types, Computable to Definable, and Syntactic Consistency 
to Semantic Consistency.  We argue for the adoption of each.  We exhibit
a programming language, Viron, that capitaizes on these shifts.


@Entry(Code "STAN-CS-82-952",
	Title "A Temporal Logic for Multi-Level Reasoning about
              Hardware",
	Author "Ben Moszkowski",
	Price "$2.75",
	Mprice "$2.00",
	Note "25 pages",
	Date "November 1982")

This paper describes a logical notation for reasoning about digital circuits.
The formalism provides a rigorous and natural basis for device specification
as well as for providing properties such as correctnes of impplementation.
Conceptual levels of circuit operation ranging from detailed quantitative
timing and signal propagation up to functional behavior are integrated in
a unified way.

A temporal predicate calculus serves as the formal core of the notation, 
resulting in a versatile tool that has more descriptive power than any
conventional hardware specification language.  The logic has been applied
to specifying and proving numerous properties of circuits ranging from delay 
elements up to the Am2901 ALU bit slice.  Presentations of a delay model
and a multiplication circuit illustrate various features of the notation.


@Entry(Code "STAN-CS-82-953",
   	Title "Paartial Bibliography of Work on Expert Systems",
	Author "Bruce G. Buchanan",
	Price "$2.45",
	Mprice "$2.00",
	Note "15 pages",
	Date "December 1982")

Since 1971 many publications on expert systems have appeared in 
conference proceedings and the technical literature.  Over 200
titles are listed in the bibliography.  Many relevant publications
are omitted because they overlap publication on the list; others
should be called to my attention.


@Entry(Code "STAN-CS-82-954",
	Title "How to Cook a Temporal Proof System for Your Pet Language",
	Author "Zohar Manna and Amir Pnueli",
	Price "$2.45",
	Mprice "$2.00",
	Note "14 pages",
	Date "December 1982")

An abstract temporal proof system is presented whose program-dependent part
has a high-level interface with the programming language actually studied.
Given a new language, it is sufficient to define the interface notions of
atomic transitions, justic, and fairness in order to obtain a full temporal
proof system for this language. This construction is particularly useful for
the analysis of concurren systems.  We illustrate the construction on the
shared-variable model and on CSP.  The generic proof system is shown to be
relatively complete with respect to pure first-order temporal logic.


@Entry(Code "STAN-CS-82-955",
	Title "Design fo an Interactive Manipulator Programming Environmnt",
 	Author "Ron Goldman",
	Price "$6.50",
	Mprice "$2.00",
	Note "90 pages",
	Date "December 1982")

This dissertation examines both the problems unique to manipulator programming
that arise from including the physical world as a part of the programming
environment and also the consequent problems of programming in this environment.
Some specific issues discussed include object definition, motion control, use
of force and compliance, error recovery, and parallelism.  Requirements for a
successful manipulator programming environment are formulated in light of these
and other problems.


@Entry(Code "STAN-CS-82-935",
	Title "Programming Language for AI Research",
	Author "Steve Tappel, Stephen Westfold, and Avron Barr",
	Price "Not available",
	Mprice "$2.00",
	Note "90 pages",
	Date "September 1982")

This report describes the programming-language features and environments
developed by AI researchers---the "tools of thought" in which new ideas
and perspectives on the understanding of cognition are first explored.
Of note here is the extended discussion of LISP--by far the most 
important tool of either kind yet invented in AI.

@Entry(Code "STAN-CS-82-936",
        Title "Models of Cognition",
        Author "Paul R. Cohen",
        Price "Not available",
        Mprice "$2.00",
        Note "87 pages",
        Date "September 1982")

This chapter, written by Paul R. Cohen, discusses AI models of human
memory, belief, and planning and problem solving.  These programs
(e.g. EPAM, GPS, and HAM) were among the earliest developed in AI
and give some insight into the powerful influence of the computer
on the development of AI and cognitive psychology.

@Entry(Code "STAN-CS-82-937",
        Title "Automatic Deduction",
        Author "Ballantyne, Bledsoe, Doyle, Moore, et al",
        Price "Not available",
        Mprice "$2.00",
        Note "64 pages",
        Date "September 1982")

Organized by Janice Aikins, this chapter on automatic deduction, also
called automatic theorem proving, describes resolution and natural-
deduction theorem proving, the Boyer-Moore theorem prover, nonmonotonic
logic, and logic programming.

@Entry(Code "STAN-CS-82-938",
        Title "Vision",
        Author "Takeo Kanade",
        Price "Not available",
        Mprice "$2.00",
        Note "220 pages",
        Date "September l982")

With contributions by David A. Bourne, Rodney Brooks, Nancy H. Cornelius,
James L. Crowley, Hiromichi Fujisawa, Martin Herman, Fuminobu Komura, Bruce
D. Lucas, Steven A. Shafer, David R. Smith, Steven L. Tanimoto, and Charles
E. Thorpe, this chapter describes all aspects of computer vision, from the 
design and calibration of cameras to preprocessing and edge detection, the
extraction of image features, and the inference of scene characteristics.
It also includes several articles on blocks-world vision research, a section
on algorithms for vision systems, and a section on applications of vision
research.

@Entry(Code "STAN-CS-82-939",
        Title "Planning and Problem Solving",
        Author "Paul R. Cohen",
        Price "Not available",
        Mprice "$2.00",
        Note "61 pages",
        Date "September 1982")

With contributions by Stephen Westfold and Peter Friedland, this chapter 
reviews nonhierarchical planning and continues on to discuss hierarchical 
and least-commitment planning and the refinement of skeletal plans.

@Entry(Code "STAN-CS-82-940",
        Title "The Equivalence of Universal Relation Definitions",
        Author "David Maier, Jeffrey Ullman, and Moshe Vardi",
        Price "$2.85",
        Mprice "$2.00",
        Note "27 pages",
        Date "September 1982")

The universal relation model aims at achieving complete access path 
independence by relieving the user of the need for logical navigation
among relations.  It assumes that for every set of attributes there is a 
basic relationship that the user has in mind.  Two fundamentally different
approaches to the universal relation model have been taken.  The first
approach sees the universal relation as a user view, about which he
poses queries.  Specifically, a representative instance is constructed, 
and queries are answered based on its non-null part.  The second approach 
sees the model as having query-processing capabilities that relieve the
user of the need to specify the logical access path.  The relationship
between the user's view and the computation answering a query is a central
issue that systems supporting a universal view of data must handle.

@Entry(Code "STAN-CS-82-941",
        Title "Integrating Local Information to Understand Dialog",
        Author "Paul Alan Martin",
        Price "Not available",
        Mprice "$2.00",
        Note "131 pages",
        Date "March 1981")

The design of computer systems capable of understanding natural language is a
long standing and important goal of Artificial Intelligence, both for its
practical benefits and for the insights it offers into human cognition.  The
task is immense, and the accomplishments in the field to date do not provide
an adequate framework to divide the problem into cleanly separable pieces.
One portion of the problem that has recently received significant attention
is the study of coherence among the individual utterances in an extended 
monolog or in discourse among speakers.  This dissertation describes a 
conceptual approach to the related problems of coherence and focus in dialog,
and the use of a computer system to study concretely some of the issues and
problems raised by this approach.

@Entry(Code "STAN-CS-82-942",
        Title "Verifying Concurrent Processes Using Temporal Logic",
        Author "Brent T. Hailpern",
        Price "Not available",
        Mprice "$2.00",
        Note "114 pages",
        Date "August 1980")

Concurrent processes can exhibit extremely complicated behavior, and neither
informal reasoning nor testing is reliable enough to establish their correctness
In this thesis, we develop a new technique for the verification of
parallel programs.  The technique is stated in terms of axioms and inference 
rules, and it is used to prove safety and liveness properties of parallel
programs.  Safety properties are assertions that must be satisfied by systems
state at all times; they are analogous to partial correctness.  Liveness
properties refer to events that will occcur in the future, such as program
termination or the eventual receipt of a message.  In addition to the formal
proof rules, we present several heuristics to aid in the preparation of
correctness proofs.

@Entry(Code "STAN-CS-82-943",
        Title "Naming Planar Graphs",
        Author "Donald R. Woods",
        Price "Not available",
        Mprice "$2.00",
        Note "58 pages",
        Date "June 1981")

Given a planar graph, we wish to draw it in the plane so that no edges 
cross.  We might be given a particular planarisation (a specification
giving the faces of the desired drawing) instead of merely the graph, but 
this is not required.  Given a planarisation and a choice of outermost face,
all drawings are in a sense equivalent; indeed, when the drawing is performed
on the surface of a sphere instead of on the plane, even the choice of outermost
face is irrelevant.  To make the problem meaningful, we must introduce
further constraints.  Two general forms of constraints are:  (1) absolute
restrictions of the details of the drawing, that is, disallowing or requiring
certain features, and (2) weighted restrictions, that is, additional objectives
to be met to whatever extent is possible.

We first examine the general problem, and look at various constraints that have 
been found to yield useful drawings in some applications.  We then examine in 
more detail one particular set of constraints, developing a fast algorithm for 
producing drawings meeting those constraints, and proving some theorems relating
to the overall complexity of the problem.  Finally, we look at what results are
known regarding other variations on the general problem.


@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))}>)