Stanford University. Computer Science Department

Per Magnus Alfred Bothner

Efficiently Combining Logical Constraints with Functions

Forest Baskett

R. R. Muntz

The authors derived the equilibrium distribution of states of a model containing four different types of service centers and R different classes of customers. From this steady state distribution one can compute the moments of the queue sizes for different classes of customers at different service centers, the usage of the service centers, the 'cycle time' or response time for different classes of customers, the 'throughput' of different classes of customers, and other measures of system performance. The model allows different classes of customers to have different arrival rates and different routing probabilities. For open networks some very simple formulas give the marginal distribution of customers at the service centers of the network. Allowing different classes of customers should answer one of the principal objections to queueing models as models of computer systems. The example given indicates how significant different classes of customers can be in the safe levels predicted by model analysis. (Modified author abstract).

Open, closed, and mixed networks of queues with different classes of customers

Stefan G. Demetrescu

Scan Line Access Memories for High Speed Image Rasterization

Donald W. Grace

To classify the polyhedra, to survey the polyhedral shapes, and to exhaust their variety by orderly enumeration is a naturally attractive problem, noticed by Euler and Jakob Steiner, to which some mathematicians, especially Max Bruckner, devoted considerable work. With the latest high-speed digital computers decades of manual labor can be compressed into hours. This dissertation is concerned with the solution of the enumeration problem on a digital computer. A tri- linear polyhedron is one in which each vertex is incident with exactly three edges. Two polyhedra are isomorphic if a one-toone correspondence can be established between the vertices, edges, and faces of one with those of the other, so that the incidence relations between elements are preserved. Two polyhedra are called equi-surrounded if a one-to-one correspondence can be established between the faces of one and the faces of the other so that each pair of corresponding faces has equivalent surroundings -- i. e. the neighbors of the two faces in question, when taken in cyclic order clockwise, display the same pattern of edge-counts. Isomorphism implies equisurroundedness. A counter-example with 18 faces disproves the converse. However, for polyhedra with up to 17 faces we can apparently equate isomorphism with equisurroundedness.

Computer Search for Non-isomorphic Convex Polyhedra

Clark A. Crane

Linear Lists and Priority Queues as Balanced Binary Trees

David R. Stoutemyer

Numerical Implementation of the Schwarz Alternating Procedure for Elliptic Partial Differential Equations

Gunnar Rutger Grape

A system for computer vision is presented, which is based on two-dimensional prototypes, and which uses a hierarchy of features for mapping purposes. More specifically, one is dealing with scenes composed of planar faced, convex objects. Extensions to the general planar faced case are discussed. The visual input is provided by a TV-camera, and the problem is to interpret that input by computer, as a projection of a three-dimensional scene. The system proposed and demonstrated in this paper uses perspectively consistent two-dimensional models (prototypes) of views of three-dimensional objects, and interpretations of scene-representations are based on the establishment of mapping relationships from conglomerates of scene-elements (line-constellations) to prototypes templates. The prototypes are learned by the program through analysis of - and generalization on - ideal instances. (Modified author abstract).

Model Based (intermediate-level) Computer Vision

R. Filman

An intelligent computer program must have both a representation of its knowledge, and a mechanism for manipulating that knowledge in a reasoning process. This thesis examines the problem of formalizing the expression and solution of reasoning problems in a machine manipulable form. It is particularly concerned with analyzing the interaction of the standard form of deductive steps with an observational analogy obtained by performing computation in a semantic model. This dissertation is centered on the world of retrograde analysis chess, a particularly rich domain for both observational tasks and long deductive sequences. A formalization is embodied in its axioms, and a major portion is devoted to both axiomatizing the rules of chess, and discussing and comparing the representational decisions involved in that axiomatization. Consideration was given not only to the necessity for these particular choices (and possible alternatives) but also the implications of these results for designers of representational systems for other domains. Using a reasoning system for first order logic, 'FOL', a detailed proof of the solution of a difficult retrograde chess puzzle was constructed. The close correspondence between this 'formal' solution to the problem, and an 'informal, descriptive' analysis a human might present was shown. The proof and axioms were then examined for their relevance to general epistemological formalisms.

The Interaction of Observation and Inference

Marianne Baudinet

Techniques and Applications

Logic Programming Semantics

Arjun Kapur

We use Linear-time Temporal Logic for expressing properties under either a sampling semantics or a super-dense semantics, and we introduce Hybrid Temporal Logic for expressing properties under a continuous interval semantics. Linear-time Temporal Logic is useful for expressing point-based properties, whose validity is dependent on individual states, while Hybrid Temporal Logic is useful for expressing both interval-based properties, whose validity is dependent on intervals of time, and point-based properties.

Interval and Point-based Approaches to Hybrid System Verification

Russell Highsmith Taylor

A Synthesis of Manipulator Control Programs from Task-level Specifications

E. W. Mayr

C. G. Plaxton

Network Implementations of the DTEP Algorithm

Eric Jonathan Schoen

Intelligent Assistance for the Design of Knowledge-based Systems

Barbara Jane Huberman

Stanford Artificial Intelligence Laboratory

A program to play chess end games is described. The model used in the program is very close to the model assumed in chess books. Embedded in the model are two predicates, better and worse, which contain the heuristics of play, different for each end game. The definitions of better and worse were obtained by programmer translation from the chess books. The program model is shown to be a good one for chess end games by the success achieved for three end games. Also the model enables us to prove that the program can reach checkmate from any starting position. Insights about translation from book problem solving methods into computer program heuristics are discussed; they are obtained by comparing the chess book methods with the definitions of better and worse, and by considering the difficulty encountered by the programmer when doing the translation. (Author).

A Program to Play Chess End Games

R. C. Bolles

Verification Vision Within a Programmable Assembly System

M. T. Kaufman

The paper considers a solution to the multiprocessor scheduling problem for the case where the ordering relation between tasks can be represented as a tree. (Modified author abstract).

An almost-optimal algorithm for the assembly line scheduling problem

Jonathan Leonard Ryder

The Japanese game of Go is of interest both as a problem in mathematical representation and as a game which generates a move tree with an extraordinarily high branching factor (100 to 300 branches per ply). The complexity of Go (and the difficulty of Go for human players) is thought to be considerably greater than that of chess. The constraints of being able to play a complete game and of being able to produce a move with a moderate amount of processing time were placed on the solution. The basic approach used was to find methods for isolating and exploring several sorts of relevant subsections of the global game tree. This process depended heavily on the ability to define and manipulate entitles of Go as recursive functions rather than as patterns of stones. A general machine-accessible theory of Go was developed to provide context for program evaluations. A program for playing Go is now available on the Stanford PDP-10 computer. (Modified author abstract).

Heuristic Analysis of Large Trees as Generated in the Game of Go

Douglas B. Lenat

A program called 'AM', is described which models one aspect of elementary mathematics research: developing new concepts under the guidance of a large body of heuristic rules. 'Mathematics' is considered as a type of intelligent behavior, not as a finished product. The local heuristics communicate via an agenda mechanism, a global list of tasks for the system to perform and reasons why each task is plausible. A single task might direct AM to define a new concept, or to explore some facet of an existing concept, or to examine some empirical data for regularities, etc. Repeatedly, the program selects from the agenda the task having the best supporting reasons, and then executes it. Each concept is an active, structured knowledge module. A hundred very incomplete modules are initially provided, each one corresponding to an elementary set-theoretic concept (e.g., union). This provides a definite but immense 'space' which AM begins to explore. AM extends its knowledge base, ultimately rediscovering hundreds of common concepts (e.g., numbers) and theorems (e.g., unique factorization). This approach to plausible inference contains great powers and great limitations.

Am: an Artificial Intelligence Approach to Discovery in Mathematics as Heuristic Search

M. L. Ginsberg

Counterfactuals are a form of commonsense non-monotonic inference that has been of long-term interest to philosophers. This paper begins by describing some of the impact counterfactuals can be expected to have in artificial intelligence, and by reviewing briefly some of the philosophical conclusions which have been drawn about them. Philosophers have noted that the content of any particular counterfactual is in part context-dependent; we present a formal description of counterfactuals that allows us to encode this context-dependent information clearly in the choice of a sublanguage of the logical language in which we are working. Having made this choice, we show that our description of counterfactuals is formally identical to the accepted possible worlds interpretation due to David Lewis. Finally, we examine the application of our ideas in the domain of automated diagnosis of hardware faults. Additional keywords: operators(mathematics); mathematical logic; semantics; artificial intelligence. (Author).

Counterfactuals

Stanford University. Computer Science Department

About

Books

Join the club