Stanford Computer Science Department Technical Reports from the 1990
The authors have given permission to make their technical reports available on this server. If a report waspublished in print and is not here it may be that the author published it elsewhere.
Report Number: CS-TR-90-1298
Institution: Stanford University, Department of Computer Science
Title: Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.
Author: Gray, Cary G.
Author: Cheriton, David R.
Date: January 1990
Abstract: Caching introduces the overhead and complexity of ensuring consistency, reducing some of its performance benefits. In a distributed system, caching must deal with the additional complications of commumcation and host failures. Leases are proposed as a time-based mechanism that provides efficient consistent access to cached data in distributed systems. Non-Byzantine failures affect performance, not correctness ,with their effect minimized by short leases. An analytic model and an evaluation for file access in the V system show that leases of short duration provide good performance. The impact of leases on performance grows more significant in systems of larger scale and higher processor performance.
CS-TR-90-1298
Report Number: CS-TR-90-1304
Institution: Stanford University, Department of Computer Science
Title: A model of object-identities and values
Author: Matsushima, Toshiyuki
Author: Wiederhold, Gio
Date: February 1990
Abstract: An algebraic formalization of the object-orlented data model is proposed. The formalism reveals that the semantics of the object-oriented model consists of two portions. One is expressed by an algebraic construct, which has essentially a value-oriented semantics. The other is expressed by object-identities, which characterize the essential difference of the object-oriented model and value-oriented models, such as the relational model and the logical database model. These two portions are integrated by a simple commutativity of modeling functions. The formalism includes the expression of integrity constraints in its construct, which provides the natural integration of the logical database model and the object-oriented database model.
CS-TR-90-1304
Report Number: CS-TR-90-1305
Institution: Stanford University, Department of Computer Science
Title: A comparative evaluation of nodal and supernodal parallel sparse matrix factorization: detailed simulation results
Author: Rathberg, Edward
Author: Gupta, Anoop
Date: February 1990
Abstract: In this paper we consider the problem of factoring a large sparse system of equations on a modestly parallel shared-memory multiprocessor with a non-trivial memory hierarchy. Using detailed multiprocessor simulation, we study the behavior of the parallel sparse factorization scheme developed at the Oak Ridge National Laboratory. We then extend the Oak Ridge scheme to incorporate the notion of supernodal elimination. We present detailed analyses of the sources of performance degradation for each of these schemes. We measure the impact of interprocessor communication costs, processor load imbalance, overheads introduced in order to distribute work, and cache behavior on overall parallel performance. For the three benchmark matrices which we study, we find that the supernodal scheme gives a factor of 1.7 to 2.7 performance advantage for 8 processors and a factor of 0.9 to 1.6 for 32 processors. The supemodal scheme exhibits higher performance due mainly to the fact that it executes many fewer memory operations and produces fewer cache misses. However, the natural task grain size for the supernodal scheme is much larger than that of the Oak Ridge scheme, making effective distnbution of work more difficult, especially when the number of processors is large.
CS-TR-90-1305
Report Number: CS-TR-90-1307
Institution: Stanford University, Department of Computer Science
Title: Real-time logics: complexity and expressiveness
Author: Alur, Rajeev
Author: Henzinger, Thomas A.
Date: March 1990
Abstract: The theory of the natural numbers with linear order and monadic predicates underlies propositional linear temporal logic. To study temporal logics for real-time systems, we combine this classical theory of infinite state sequences with a theory of time, via a monotonic function that maps every state to its time. The resulting theory of timed state sequences is shown to be decidable, albeit nonelementary, and its expressive power is characterized by omega-regular sets. Several more expressive variants are proved to be highly undecidable. This framework allows us to classify a wide variety of real-time logics according to their complexity and expressiveness. In fact, it follows that most formalisms proposed in the literature cannot be decided. We are, however, able to identify two elementary real-time temporal logics as expressively complete fragments of the theory of timed state sequences, and give tableau-based decision procedures. Consequently, these two formalisms are well-suited for the specification and verification of real-time systems.
CS-TR-90-1307
Report Number: CS-TR-90-1312
Institution: Stanford University, Department of Computer Science
Title: A validation structure based theory of plan modification and reuse
Author: Kambhampati, Subbarao
Author: Hendler, James A.
Date: June 1990
Abstract: A framework for the flexible and conservative modification of plans enables a planner to modify its plans in response to incremental changes in their specifications, to reuse its existing plans in new problem situations, and to efficiently replan in response to execution time failures. We present a theory of plan modification applicable to hierarchical nonlinear planning. Our theory utilizes the validation structure of stored plans to yield a flexible and conservative plan modification framework. The validation structure, which constitutes a hierarchical explanation of correctness of the plan with respect to the planner's own knowledge of the domain, is annotated on the plan as a by-product of initial planning. Plan modification is formalized as a process of removing inconsistencies in the validation structure of a plan when it is being reused in a new (changed) planning situation. The repair of these inconsistencies involves removing unnecessary parts of the plan and adding new non-primitive tasks to the plan to establish missing or failing validations. The resultant partially reduced plan (with a consistent validation structure) is sent to the planner for complete reduction. We discuss the development of this theory in the PRIAR system, present an empirical evaluation of this theory, and characterize its completeness, coverage, efficiency and limitations.
CS-TR-90-1312
Report Number: CS-TR-90-1313
Institution: Stanford University, Department of Computer Science
Title: Book review: Potokovye Algoritmy (Flow Algorithms) by G. M. Adel'son-Vel'ski, E. A. Dinic, and A. V. Karzanov.
Author: Goldberg, Andrew V.
Author: Gusfield, Dan
Date: June 1990
Abstract: This is a review of the book "Flow Algorithms" by Adel'son-Vel'ski, Dinic, and Karzanov, well-known researchers in the area of algorithm design and analysis. This remarkable book, published in 1975, is written in Russian and has never been translated into English. What is remarkable about the book is that it describes many major results obtained in the Soviet Union (and originally published in papers by 1976) that were independently discovered later (and in some cases much later) in the West. The book also contains some minor results that we believe are still unknown in the West. The book is well-written and a pleasure to read, at least for someone fluent in Russian. Although the book is fifteen years old and we believe that all the major results contained in it are known in the West by now, the book is still of great historical importance. Hence a complete review is in order. [from the Introduction]
CS-TR-90-1313
Report Number: CS-TR-90-1314
Institution: Stanford University, Department of Computer Science
Title: Genetic programming: a paradigm for genetically breeding populations of computer programs to solve problems
Author: Koza, John R.
Date: June 1990
Abstract: Many seemingly different problems in artificial intelligence, symbolic processing, and machine learning can be viewed as requiring discovery of a computer program that produces some desired output for particular inputs. When viewed in this way, the process of solving these problems becomes equivalent to searching a space of possible computer programs for a most fit individual computer program. The new "genetic programming" paradigm described herein provides a way to search for this most fit individual computer program. In this new "genetic programming" paradigm, populations of computer programs are genetically bred using the Darwinian principle of survival of the fittest and using a genetic crossover (recombination) operator appropriate for genetically mating computer programs. In this paper, the process of formulating and solving problems using this new paradigm is illustrated using examples from various areas. Examples come from the areas of machine learning of a function; planning; sequence induction; function function identification (including symbolic regression, empirical discovery, "data to function" symbolic integration, "data to function" symbolic differentiation); solving equations, including differential equations, integral equations, and functional equations); concept formation; automatic programming; pattern recognition, time-optimal control; playing differential pursuer-evader games; neural network design; and finding a game-playing strategyfor a discrete game in extensive form.
CS-TR-90-1314
Report Number: CS-TR-90-1318
Institution: Stanford University, Department of Computer Science
Title: Techniques for improving the performance of sparse matrix factorization on multiprocessor workstations
Author: Rothberg, Edward
Author: Gupta, Anoop
Date: June 1990
Abstract: In this paper we look at the problem of factoring large sparse systems of equations on high-performance multiprocessor workstations. While these multiprocessor workstations are capable of very high peak floating point computation rates, most existing sparse factorization codes achieve only a small fraction of this potential. A major limiting factor is the cost of memory accesses performed during the factorization. ln this paper, we describe a parallel factorization code which utilizes the supernodal structure of the matrix to reduce the number of memory references. We also propose enhancements that significantly reduce the overall cache miss rate. The result is greatly increased factorization performance. We present experimental results from executions of our codes on the Silicon Graphics 4D/380 multiprocessor. Using eight processors, we find that the supernodal parallel code achieves a computation rate of approximately 40 MFLOPS when factoring a range of benchmark matrices. This is more than twice as fast as the parallel nodal code developed at the Oak Ridge National Laboratory running on the SGI 4D/380.
CS-TR-90-1318
Report Number: CS-TR-90-1321
Institution: Stanford University, Department of Computer Science
Title: Tools and rules for the practicing verifier
Author: Manna, Z ohar
Author: Pnueli, Amir
Date: July 1990
Abstract: The paper presents a minimal proof theory which is adequate for proving the main important temporal properties of reactive programs. The properties we consider consist of the classes of invariance, response, and precedence properties. For each of these classes we present a small set of rules that is complete for verifying properties belonging to this class. We illustrate the application of these rules by analyzing and verifying the properties of a new algorithm for mutual exclusion.
CS-TR-90-1321
Report Number: CS-TR-90-1323
Institution: Stanford University, Department of Computer Science
Title: Protograms
Author: Mozes, Eyal
Author: Shoham, Yoav
Date: July 1990
Abstract: Motivated largely by tasks that require control of complex processes in a dynamic environment, we introduce a new computational construct called a protogram. A protogram is a program specifying an abstract course of action, a course that allows for a range of specific actions, from which a choice is made through interaction with other protograms. We discuss the intuition behind the notion, and then explore some of the details involved in implementing it. Specifically, we (a) describe a general scheme of protogram interaction, (b) describe a protogram interpreter that has been implemented, dealing with some special cases, (c) describe three applications of the protogram interpreter, one in data processing and two in robotics (both currently only implemented as simulations), (d) describe some more general possible implementations of a protogram interpreter, and (e) discuss how protograms can be useful for the Gofer project. We also briefly discuss the origins of protograms in psychology and linguistics, compare protograms to blackboard and subsumption architectures, and discuss directions for future research.
CS-TR-90-1323
Report Number: CS-TR-90-1324
Institution: Stanford University, Department of Computer Science
Title: On the complexity of monotonic inheritance with roles
Author: Guerreiro, Ramiro A. de T.
Author: Hemerly, S.
Author: Shoham, Yoav
Date: July 1990
Abstract: We investigate the complexity of reasoning with monotonic inheritance hierarchies that contain, beside ISA edges, also ROLE (or FUNCTION) edges. A ROLE edge is an edge labelled with a name such as spouse of or brother of. We call such networks ISAR networks. Given a network with n vertices and m edges, we consider two problems: ($P_1$) determining whether the network implies an isa relation between two particular nodes, and ($P_2$) determining all isa relations implied by the network. As is well known, without ROLE edges the time complexity of $P_1$, is O(m), and the time complexity of $P_2$ is O($n^3$). Unfortunately, the results do not extend naturally to ISAR networks, except in a very restricted case. For general ISAR network we first give an polynomial algorithm by an easy reduction to proposional Horn theory. As the degree of the polynomial is quite high (O(m$n^4$) for $P_1$, O(m$n^6$) for $P_2$), we then develop a more direct algorithm. For both $P_1$ and $P_2$ its complexity is O($n^3 + m^2$). Actually, a finer analysis of the algorithm reveals a complexity of O(nr(log r) + $n^2$r+ $n^3), where r is the number of different ROLE labels. One corolary is that if we fix the number of ROLE labels, the complexity of our algorithm drops back to O($n^3$).
CS-TR-90-1324
Report Number: CS-TR-90-1329
Institution: Stanford University, Department of Computer Science
Title: An interleaving model for real time.
Author: Henzinger, Thomas A.
Author: Manna, Z ohar
Author: Pnueli, Amir
Date: September 1990
Abstract: The interleaving model is both adequate and sufficiently abstract to allow for the practical specification and verification of many properties of concurrent systems. We incorporate real time into this model by defining the abstract notion of a real-time transition system as a conservative extension of traditional transition systems: qualitative fairness requirements are replaced (and superseded) by quantitative lower-bound and upper-bound real-time requirements for transitions. We present proof rules to establish lower and upper real-time bounds for response properties of real-time transition systems. This proof system can be used to verify bounded-invariance and bounded-response properties, such as timely terrnination of shared-variables multi-process systems, whose semantics is defined in terms of real-time transition systems.
CS-TR-90-1329
Report Number: CS-TR-90-1330
Institution: Stanford University, Department of Computer Science
Title: Parallel ICCG on a hierarchical memory multiprocessor - addressing the triangular solve bottleneck
Author: Rothberg, Edward
Author: Gupta, Anoop
Date: October 1990
Abstract: The incomplete Cholesky conjugate gradient (ICCG) algorithm is a commonly used iterative method for solving large sparse systems of equations. In this paper, we study the parallel solution of sparse triangular systems of equations, the most difficult aspect of implementing the ICCG method on a multiprocessor. We focus on shared-memory multiprocessor architectures with deep memory hierarchies. On such architectures we find that previously proposed parallelization approaches result in little or no speedup. The reason is that these approaches cause significant increases in the amount of memory system traffic as compared to a sequential approach. Increases of as much as a factor of 10 on four processors were observed. In this paper we propose new techniques for limiting these increases, including data remappings to increase spatial locality, new processor synchronization techniques to decrease the use of auxiliary data structures, and data partitioning techniques to reduce the amount of interprocessor communication. With these techniques, memory system traffic is reduced to as little as one sixth of its previous volume. The resulting speedups are greatly improved as well, although they are still much less than linear. We discuss the factors that limit further speedups. We present both simulation results and results of experiments on an SGI 4D/340 multiprocessor.
CS-TR-90-1330
Report Number: CS-TR-90-1337
Institution: Stanford University, Department of Computer Science
Title: A simplifier for untyped lambda expressions
Author: Galbiati, Louis
Author: Talcott, Carolyn
Date: October 1990
Abstract: Many applicative programming languages are based on the call-by-value lambda calculus. For these languages tools such as compilers, partial evaluators, and other transformation systems often make use of rewriting systems that incorporate some form of beta reduction. For purposes of automatic rewriting it is important to develop extensions of beta-value reduction and to develop methods for guaranteeing termination. This paper describes an extension of beta-value reduction and a method based on abstract interpretation for controlling rewriting to guarantee termination. The main innovations are (1) the use of rearrangement rules in combination with beta-value reduction to increase the power of the rewriting system and (2) the definition of a non-standard interpretation of expressions, the generates relation, as a basis for designing terminating strategies for rewriting.
CS-TR-90-1337
Report Number: CS-TR-90-1340
Institution: Stanford University, Department of Computer Science
Title: Programming in QLisp
Author: Mason, Ian A.
Author: Pehoushek, Joseph D.
Author: Talcott, Carolyn L.
Author: Weening, Joseph S.
Date: October 1990
Abstract: Qlisp is an extension of Common Lisp, to support parallel programming. It was initially designed by John McCarthy and Richard Gabriel in 1984. Since then it has been under development both at Stanford University and Lucid, Inc. and has been implemented on several commercial shared-memory parallel computers. Qlisp is a queue-based, shared-memory, multi-processing language. This report is a tutorial introduction to the Stanford dialect of Qlisp.
CS-TR-90-1340
Report Number: CS-TR-90-1342
Institution: Stanford University, Department of Computer Science
Title: Modeling concurrency with geometry
Author: Pratt, Vaughan
Date: November 1990
Abstract: The phenomena of branching time and true or noninterleaving concurrency find their respective homes in automata and schedules. But these two models of computation are formally equivalent via Birkhoff duality, an equivalence we expound on here in tutorial detail. So why should these phenomena prefer one over the other? We identify dimension as the culprit: 1-dimensional automata are skeletons permitting only interleaving concurrency, whereas rrue n-fold concurrency resides in transitions of dimension n. The truly concurrent automaton dual to a schedule is not a skeletal distributive lattice but a solid one! We introduce true nondeterminism and define it as monoidal homotopy; from this perspective nondeterminism in ordinary automata arises from forking and joining creating nontrivial homotopy. The automaton dual to a poset schedule is simply connected whereas that dual to an event structure schedule need not be, according to monoidal homotopy though not to group homotopy. We conclude with a formal definition of higher dimensional automaton as an n-complex or n-category, whose two essential axioms are associativity of concatenation within dimension and an interchange principle between dimensions.
CS-TR-90-1342
Report Number: CS-TR-90-1343
Institution: Stanford University, Department of Computer Science
Title: Action logic and pure induction
Author: Pratt, Vaughan
Date: November 1990
Abstract: In Floyd-Hoare logic, programs are dynamic while assertions are static (hold at states). In action logic the two notions become one, with programs viewed as on-the-fly assertions whose truth is evaluated along intervals instead of at states. Action logic is an equational theory ACT conservatively extending the equational theory REG of regular expressions with operations preimplication a --> b (had a then b) and postimplication b <-- a (b if-ever a). Unlike REG, ACT is finitely based, makes $a^*$ reflexive transitive closure, and has an equivalent Hilbert system. The crucial axiom is that of pure induction, ${(a --> a)}^*$ = a --> a.
CS-TR-90-1343
Report Number: CS-TR-90-1344
Institution: Stanford University, Department of Computer Science
Title: ParaDiGM: a highly scalable shared-memory multi-computer architecture
Author: Cheriton, David R.
Author: Goosen, Hendrik A.
Author: Boyle, Patrick D.
Date: November 1990
Abstract: ParaDiGM is a highly scalable shared-memory multi-computer architecture. It is being developed to demonstrate the feasibility of building a relatively low-cost shared-memory parallel computer that scales to large configurations, and yet provides sequential programs with performance comparable to a high-end microprocessor. A key problem is building a scalable memory hierarchy. In this paper we describe the ParaDiGm architecture, highlighting the innovations of our approach and presenting results of our evaluation of the design. We envision that scalable shared-memory multiprocessors like ParaDiGM will soon become the dominant form of parallel processing, even for very large-scale computation, providing a uniform platform for parallel programming systems and applications.
CS-TR-90-1344
Report Number: CS-TR-90-1345
Institution: Stanford University, Department of Computer Science
Title: Nonholonomic motion planning versus controllability via the multibody car system example
Author: Laumond, Jean-Paul
Date: December 1990
Abstract: A multibody car system is a non-nilpotent, non-regular, triangularizable and well-controllable system. One goal of the current paper is to prove this obscure assertion. But its main goal is to explain and enlighten what it means. Motion planning is an already old and classical problem in Robotics. A few years ago a new instance of this problem has appeared in the literature: motion planning for nonholonomic systems. While useful tools in motion planning come from Computer Science and Mathematics (Computational Geometry, Real Algebraic Geometry), nonholonomic motion planning needs some Control Theory and more Mathematics (Differential Geometry). First of all, this paper tries to give a computational reading of the tools from Differential Geometric Control Theory required by planning. Then it shows that the presence of obstacles in the real world of a real robot challenges Mathematics with some difficult questions which are topological in nature, and have been solved only recently, within the framework of Sub-Riemannian Geometry. This presentation is based upon a reading of works recently developed by (1) Murray and Sastry, (2) Lafferiere and Sussmann, and (3) Bellaiche, Jacobs and Laumond.
CS-TR-90-1345
Report Number: CS-TR-91-1350
Institution: Stanford University, Department of Computer Science
Title: A programming and problem solving seminar.
Author: Chang, Edward
Author: Phillips, Steven J.
Author: Ullman, Jeffrey D.
Date: February 1991
Abstract: This report contains transcripts of the classroom discussions of Stanford's Computer Science problem solving course for Ph.D. students, CS304, during Winter quarter 1990, and the first CS204 class for undergraduates, in the Spring of 1990. The problems, and the solutions offered by the classes, span a large range of ideas in computer science. Since they constitute a study both of programming and research paradigms, and of the problem solving process, these notes may be of interest to students of computer science, as well as computer science educators. The present report is the ninth in a series of such transcripts, continuing the tradition established in STAN-CS-77-606 (Michael J. Clancy, 1977), STAN-CS-79-707 (Chris Van Wyk, 1979), STAN-CS-81-863 (Allan A. Miller, 1981), STAN-CS-83-989 (Joseph S. Weening, 1983), STAN-CS-83-990 (John D. Hobby, 1983), STAN-CS-85-1055 (Ramsey W. Haddad, 1985), STAN-CS-87-1154 (Tomas G. Rokicki, 1987), and STAN-CS-89-1269 (Kenneth A. Ross, 1989).
CS-TR-91-1350
Report Number: CS-TR-91-1351
Institution: Stanford University, Department of Computer Science
Title: Sequence vs. pipeline parallel multiple joins in Paradata
Author: Z hu, Liping
Author: Keller, Arthur M.
Author: Wiederhold, Gio
Date: February 1991
Abstract: In this report we analyze and compare hash-join based parallel multi-join algorithms for sequenced and pipelined processing. The BBN Butterfly machine serves as the host for the performance analysis. The sequenced algorithm handles the multiple join operations in a conventional sequenced manner, except that it distributes the work load of each operation among all processors. The pipelined algorithms handle the different join operations in parallel, by dividing the processors into several groups, with the data flowing through these groups. The detailed timing tests revealed the bus/memory contention that grows linearly with the number of processors. The existence of such a contention leads to an optimal region for the number of processors, given the join operands fixed. We present the analytical and experimental formulae for both algorithms, which incorporate this contention. We discuss the way of finding an optimal point, and give the heuristics for choosing the best processor's partition in pipelined processing. The study shows that the pipelined algorithms produce the first joined result sooner than the sequenced algorithm and need less memory to store the intermediate result. The sequenced algorithm, on the other hand, takes less time to finish the whole join operations.
CS-TR-91-1351
Report Number: CS-TR-91-1359
Institution: Stanford University, Department of Computer Science
Title: The benefits of relaxing punctuality
Author: Alur, Rajeev
Author: Feder, Tomas
Author: Henzinger, Thomas A.
Date: May 1991
Abstract: The most natural, compositional way of modeling real-time systems uses a dense domain for time. The satisfiability of real-time constraints that are capable of expressing punctuality in this model is, however, known to be undecidable. We introduce a temporal language that can constrain the time difference between events only with finite (yet arbitrary) precision and show the resulting logic to be EXPSPACE-complete. This result allows us to develop an algorithm for the verification of timing properties of real-time systems with a dense semantics.
CS-TR-91-1359
Report Number: CS-TR-91-1360
Institution: Stanford University, Department of Computer Science
Title: Sooner is safer than later.
Author: Henzinger, Thomas A.
Date: May 1991
Abstract: It has been repeatedly observed that the standard safety-liveness classification of properties of reactive systems does not fit for real-time properties. This is because the implicit "liveness" of time shifts the spectrum towards the safety side. While, for example, response--that "something good" will happen, eventually--is a classical liveness property, bounded response--that "something good" will happen soon, within a certain amount of time--has many characteristics of safety. We account for this phenomenon formally by defining safety and liveness relative to a given condition, such as the progress of time.
CS-TR-91-1360
Report Number: CS-TR-91-1369
Institution: Stanford University, Department of Computer Science
Title: Approximating matchings in parallel
Author: Fischer, Ted
Author: Goldberg, Andrew V.
Author: Plotkin, Serge
Date: June 1991
Abstract: We show that for any constant k > O, a matching with cardinality at least 1 - 1/(k+1) times the maximum can be computed in NC.
CS-TR-91-1369
Report Number: CS-TR-91-1370
Institution: Stanford University, Department of Computer Science
Title: An NQTHM mechanization of "An Exercise in the Verification of Multi-Process Programs"
Author: Nagayama, Misao
Author: Talcott, Carolyn
Date: June 1991
Abstract: This report presents a formal verification of the local correctness of a mutex algorithm using the Boyer-Moore theorem prover. The formalization follows closely an informal proof of Manna and Pnuelli. The proof method of Manna and Pnueli is to first extract from the program a set of states and induced transition system. One then proves suitable invariants. There are two variants of the proof. In the first (atomic) variant, compound tests involving quantification over a finite set are viewed as atomic operations. In the second (molecular) variant, this assumption is removed, making the details of the transitions and proof somewhat more complicated. The original Manna-Pnueli proof was formulated in terms of finite sets. This led to concise and elegant informal proof, however one that is not easy to mechanize in the Boyer-Moore logic. In the mechanized version we use a dual isomorphic representation of program states based on finite sequences. Our approach was to outline the formal proof of each invariant, making explicit the case analyses, assumptions and properties of operations used. The outline served as our guide in developing the formal proof. The resulting sequence of events follows the informal plan quite closely. The main difficulties encountered were in discovering the precise form of the lemmas and hints necess to guide the theorem prover.
CS-TR-91-1370
Report Number: CS-TR-91-1374
Institution: Stanford University, Department of Computer Science
Title: Polynomial dual network simplex algorithms
Author: Orlin, James B.
Author: Plotkin, Serge A.
Author: Tardos, Eva
Date: August 1991
Abstract: We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m2 log n) bound on the number of pivots, where n and m denotes the number of nodes and arcs in the input network. If the demands are integral and at most B, we also give an O(m(m + n log n) min(log nB, m log n))-time implementation of a strategy that requires somewhat more pivots.
CS-TR-91-1374
Report Number: CS-TR-91-1375
Institution: Stanford University, Department of Computer Science
Title: Fast approximation algorithms for multicommodity flow problems
Author: Leighton, Tom
Author: Makedon, Fillia
Author: Plotkin, Serge
Author: Stein, Clifford
Author: Tardos, Eva
Author: Tragoudas, Spyros
Date: August 1991
Abstract: In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. Our algorithms are significantly faster than the best previously known algorithms, that were based on linear programming. For a k-commodity multicommodity flow problem, the running time of our randomized algorithm is (up to log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation. Given any multicommodity flow problem as input, our algorithm is guaranteed to provide a feasible solution to a modified flow problem in which all capacities are increased by a (1 + epsilon)-factor, or to provide a proof that there is no feasible solution to the original problem. We also describe faster approximation algorithms for multicommodity flow problems with a special structure, such as those that arise in the "sparsest cut" problems and the uniform concurrent flow problems if k <= the square root of m.
CS-TR-91-1375
Report Number: CS-TR-91-1377
Institution: Stanford University, Department of Computer Science
Title: An evaluation of left-lookikng, right-looking and multifrontal approaches to sparse Cholesky factorization on hierarchical memory machines
Author: Rothberg, Edward
Author: Gupta, Anoop
Date: August 1991
Abstract: In this paper we present a comprehensive analysis of the performance of a variety of sparse Cholesky factorization methods on hierarchical-memory machines. We investigate methods that vary along two different axes. Along the first axis, we consider three different high-level approaches to sparse factorization: left-looking, right-looking, and multifrontal. Along the second axis, we consider the implementation of each of these high-level approaches using different sets of primitives. The primitives vary based on the structures they manipulate. One important structure in sparse Cholesky factorization is a single column of the matrix. We first consider primitives that manipulate single columns. These are the most commonly used primitives for expressing the sparse Cholesky computation. Another important structure is the supernode, a set of columns with identical non-zero structures. We consider sets of primitives that exploit the supemodal structure of the matrix to varying degrees. We find that primitives that manipulate larger structures greatly increase the amount of exploitable data reuse, thus leading to dramatically higher perfommance on hierarchical-memory machines. We observe performance increases of two to three times when comparing methods based on primitives that make extensive use of the supernodal structure to methods based on primitives that manipulate columns. We also find that the overall approach (left-looking, right-looking, or multifrontal) is less important for performance than the particular set of primitives used to implement the approach.
CS-TR-91-1377
Report Number: CS-TR-91-1381
Institution: Stanford University, Department of Computer Science
Title: Implementing hypertext database relationships through aggregations and exceptions
Author: Hara, Yoshinori
Author: Keller, Arthur M.
Author: Rathmann, Peter K.
Author: Wiederhold, Gio
Date: September 1991
Abstract: In order to combine hypertext with database facilities, we show how to extract an effective storage structure from given instance relationships. The schema of the structure recognizes clusters and exceptions. Extracting high-level structures is useful for providing a high performance browsing environment as well as efficient physical database design, especially when handling large amounts of data. This paper focuses on a clustering method, ACE, which generates aggregations and exceptions from the original graph structure in order to capture high level relationships. The problem of minimizing the cost function is NP-complete. We use a heuristic approach based on an extended Kernighan-Lin algorithm. We demonstrate our method on a hypertext application and on a standard random graph, compared with its analytical model. The storage reductions of input database size in main memory were 77.2% and 12.3%, respectively. It was also useful for secondary storage organization for efflcient retrieval.
CS-TR-91-1381
Report Number: CS-TR-91-1383
Institution: Stanford University, Department of Computer Science
Title: Temporal proof methodologies for real-time systems
Author: Henzinger, Thomas A.
Author: Manna, Z ohar
Author: Pnueli, Amir
Date: September 1991
Abstract: We extend the specification language of temporal logic, the corresponding verification framework, and the underlying computational model to deal with real-time properties of reactive systems. The abstract notion of timed transition systems generalizes traditional transition systems conservatively: qualitative fairness requirements are replaced (and superseded) by quantitative lower-bound and upper-bound timing constraints on transitions. This framework can model real-time systems that communicate either through shared variables or by message passing and real-time issues such as time-outs, process priorities (interrupts), and process scheduling. We exhibit two styles for the specification of real-time systems. While the first approach uses bounded versions of temporal operators, the second approach allows explicit references to time through a special clock variable. Corresponding to the two styles of specification, we present and compare two fundamentally different proof methodologies for the verification of timing requirements that are expressed in these styles. For the bounded-operatoT style, we provide a set of proof rules for establishing bounded-invariance and bounded-response properties of timed transition systems. This approach generalizes the standard temporal proof rules for verifying invariance and response properties conservatively. For the explicit-clock style, we exploit the observation that every time-bounded property is a safety property and use the standard temporal proof rules for establishing safety properties.
CS-TR-91-1383
Report Number: CS-TR-91-1387
Institution: Stanford University, Department of Computer Science
Title: Assembling polyhedra with single translations
Author: Wilson, Randall
Author: Schweikard, Achim
Date: October 1991
Abstract: The problem of partitioning an assembly of polyhedral objects into two subassemblies that can be separated arises in assembly planning. We describe an algorithm to compute the set of all translations separating two polyhedra with n vertices in O(n4) steps and show that this is optimal. Given an assembly of k polyhedra with a total of n vertices, an extension of this algorithm identifies a valid translation and removable subassembly in O(k2 n4) steps if one exists. Based on the second algorithm a polynomial time method for finding a complete assembly sequence consisting of single translations is derived. An implementation incorporates several changes to achieve better average-case performance; experimental results obtained for composite objects consisting of isothetic polyhedra are described.
CS-TR-91-1387
Report Number: CS-TR-91-1389
Institution: Stanford University, Department of Computer Science
Title: The AGENT0 manual
Author: Torrance, Mark C.
Author: Viola, Paul A.
Date: April 1991
Abstract: This document describes an implementation of AOP, an interpreter for programs written in a language called AGENTO. AGENTO is a first stab at a programming language for the paradigm of Agent-Oriented Programming. It is currently under development at Stanford under the direction of Yoav Shoham. This implementation is the work of Paul A. Viola of MIT and Mark C. Torrance of Stanford.
CS-TR-91-1389
Report Number: CS-TR-91-1391
Institution: Stanford University, Department of Computer Science
Title: A logic for perception and belief
Author: Shoham, Yoav
Author: del Val, Alvaro
Date: September 1991
Abstract: We present a modal logic for reasoning about perception and belief, captured respectively by the operators P and B. The B operator is the standard belief operator used in recent years, and the P operator is similarly defined. The contribution of the paper is twofold. First, in terms of P we provide a definition of perceptual indistinguishability, such as arises out of limited visual acuity. The definition is concise, intuitive (we find), and avoids traditional paradoxes. Second, we explore the bimodal B--P system. We argue that the relationship between the two modalities varies among settings: The agent may or may not have confidence in its perception, may or may not be accurate in it, and so on. We therefore define a number of agent types corresponding to these various assumptions, and for each such agent type we provide a sound and complete axiomatization of the B--P system.
CS-TR-91-1391
Report Number: CS-TR-91-1392
Institution: Stanford University, Department of Computer Science
Title: A classification of update methods for replicated databases
Author: Ceri, Stefano
Author: Houtsma, Maurice A. W.
Author: Keller, Arthur M.
Author: Samarati, Pierangela
Date: October 1991
Abstract: In this paper we present a classification of the methods for updating replicated databases. The main contribution of this paper is to present the various methods in the context of a structured taxonomy, which accommodates very heterogeneous methods. Classes of update methods are presented through their general properties, such as the invariants that hold for them. Methods are reviewed both in their normal and abnormal behaviour (e.g., after a network partition). We show that several methods presented in the literature, sometimes in independent papers with no cross-reference, are indeed very much related, for instance because they share the same basic technique. We also show in what sense they diverge from the basic technique. This classification can serve as a basis for choosing the method that is most suitable to a specific application. It can also be used as a guideline to researchers who aim at developing new mechanisms.
CS-TR-91-1392
Report Number: CS-TR-91-1394
Institution: Stanford University, Department of Computer Science
Title: Application-controlled physical memory using external page-cache management
Author: Harty, Kieran
Author: Cheriton, David R.
Date: October 1991
Abstract: Next generation computer systems will have gigabytes of physical memory and processors in the 100 MIPS range or higher. Contrary to some conjectures, this trend requires more sophisticated memory management support for memory-bound computations such as scientific simulations and systems such as large-scale database systems, even though memory management for most programs will be less of a concern. We describe the design, implementation and evaluation of a virtual memory system that provides application control of physical memory using external page-cache management. In this approach, a sophisticated application is able to monitor and control the amount of physical memory it has available for execution, the exact contents of this memory, and the scheduling and nature of page-in and page-out using the abstraction of a physical page cache provided by the kernel. We claim that this approach can significantly improve performance for many memory-bound applications while reducing kernel complexity, yet does not complicate other applications or reduce their performance.
CS-TR-91-1394
Report Number: CS-TR-92-1401
Institution: Stanford University, Department of Computer Science
Title: The performance impact of data reuse in parallel dense Cholesky factorization
Author: Rothberg, Edward
Author: Gupta, Anoop
Date: January 1992
Abstract: This paper explores performance issues for several prominent approaches to parallel dense Cholesky factorization. The primary focus is on issues that arise when blocking techniques are integrated into parallel factorization approaches to improve data reuse in the memory hierarchy. We first consider panel-oriented approaches, where sets of contiguous columns are manipulated as single units. These methods represent natural extensions of the column-oriented methods that have been widely used previously. On machines with memory hierarchies, panel-oriented methods significantly increase the achieved performance over column-oriented methods. However, we find that panel- oriented methods do not expose enough concurrency for problems that one might reasonably expect to solve on moderately parallel machines, thus significantly limiting their performance. We then explore block-oriented approaches, where square submatrices are manipulated instead of sets of columns. These methods greatly increase the amount of available concurrency, thus alleviating the problems encountered with panel-oriented methods. However, a number of issues, including scheduling choices and block- placement issues, complicate their implementation. We discuss these issues and consider approaches that solve the resulting problems. The resulting block-oriented implementation yields high processor utilization levels over a wide range of problem sizes.
CS-TR-92-1401
Report Number: CS-TR-92-1412
Institution: Stanford University, Department of Computer Science
Title: Toward agent programs with circuit semantics
Author: Nilsson, Nils J.
Date: January 1992
Abstract: New ideas are presented for computing and organizing actions for autonomous agents in dynamic environments - environments in which the agent's current situation cannot always be accurately discerned and in which the effects of actions cannot always be reliably predicted. The notion of "circuit semantics" for programs based on "teleo-reactive trees" is introduced. Program execution builds a combinational circuit which receives sensory inputs and controls actions. These formalisms embody a high degree of inherent conditionality and thus yield programs that are suitably reactive to their environments. At the same time, the actions computed by the programs are guided by the overall goals of the agent. The paper also speculates about how programs using these ideas could be automatically generated by artificial intelligence planning systems and adapted by learning methods.
CS-TR-92-1412
Report Number: CS-TR-92-1419
Institution: Stanford University, Department of Computer Science
Title: Fast approximation algorithms for fractional packing and covering problems
Author: Plotkin, Serge A.
Author: Shmoys, David B.
Author: Tardos, Eva
Date: November 1993
Abstract: This paper presents fast algorithms that find approximate solutions for a general class of problems, which we call fractional packing and covering problems. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed in this paper greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. Our algorithm is a Lagrangean relaxation technique; an important aspect of our results is that we obtain a theoretical analysis of the running time of a Lagrangean relaxation-based algorithm. We give several applications of our algorithms. The new approach yields several orders of magnitude of improvement over the best previously known running times for the scheduling of unrelated parallel machines in both the preemptive and the non-preemptive models, for the job shop problem, for the cutting-stock problem, and for the minimum cost multicommodity flow problem.
CS-TR-92-1419
Report Number: CS-TR-92-1423
Institution: Stanford University, Department of Computer Science
Title: Time-lapse snapshots
Author: Dwork, Cynthia
Author: Herlihy, Maurice
Author: Plotkin, Serge A.
Author: Waarts, Orli
Date: November 1993
Abstract: Abstract. A snapshot scan algorithm takes an "instantaneous" picture of a region of shared memory that may he updated by concurrent processes. Many complex shared memory algorithms can be greatly simplified by structuring them around the snapshot scan abstraction. Unforinnately, the substantial decrease in conceptual complity is quite often counterbalanced by an increase in computational complexity. In this paper, we introduce the notion of a weak snapshot scan, a slightly weaker primitive that has a more efficient implementation. We propose the following methodology for using this abstraction: first, design and verify an algorithm using the more powerful snapshot scan, and second, replace the more powerful but less efficient snapshot with the weaker but more efficient snapshot, and show that the weaker abstraction nevertheless suffices to ensure the correctness of the enclosing algorithm. We give two examples of algorithms whose performance can be enhanced while retaining a simple modular structure: bounded concurrent timestamping, and bounded randomized consensus. The resulting timestamping protocol is the fastest known bounded concurrent timestamping protocol. The resulting randomized consensus protocol matches the computational complexity of the best known protocol that uses only bouned values.
CS-TR-92-1423
Report Number: CS-TR-92-1426
Institution: Stanford University, Department of Computer Science
Title: Proceedings of the ACM SIGPLAN Workshop on Continuations CW92
Author: Danvy, Olivier (ed.)
Author: Talcott, Carolyn (ed.)
Date: November 1993
Abstract: The notion of continuation is ubiquitous in many different areas of computer science, including logic, constructive mathematics, programming languages, and programming. This workshop aims at providing a forum for discussion of: new results and work in progress; work aimed at a better understanding of the nature of continuations; applications of continuations, and the relation of continuations to other areas of logic and computer science. This technical report serves as informal proceedings for CW92. It consists of submitted manuscripts bound together according to the program order.
CS-TR-92-1426
Report Number: CS-TR-92-1431
Institution: Stanford University, Department of Computer Science
Title: Aggressive transmissions over redundant paths for time critical messages
Author: Kao, Ben
Author: Garcia-Molina, Hector
Author: Barbara, Daniel
Date: October 1993
Abstract: Fault tolerant computer systems have redundant paths connecting their components. Given these paths, it is possible to use aggressive techniques to reduce the average value and variability of the response time for critical messages. One technique is to send a copy of a packet over an alternate path before it is known if the first copy failed or was delayed. A second technique is to split a single stream of packets over multiple paths. We analize both approaches and show that they can provide significant improvements over conventional, conservative mechanisms.
CS-TR-92-1431
Report Number: CS-TR-92-1432
Institution: Stanford University, Department of Computer Science
Title: Overview of multidatabase transaction management
Author: Breitbart, Yuri
Author: Garcia-Molina, Hector
Author: Silberschatz, Avi
Date: October 1993
Abstract: A multidatabase system (MDBS) is a facility that allows users access to data located in multiple autonomous database management systems (DBMSs). In such a system, global transactions are executed under the control of the MDBS. Independently, local transactions are executed under the control of the local DBMSs. Each local DBMS integrated by the MDBS may employ a different transaction management scheme. In addition, each local DBMS has complete control over all transactions (global and local) executing at its site, including the ability to abort at any point any of the transactions executing at its site. Typically, no design or internal DBMS structure changes are allowed in order to accommodate the MDBS. Furthermore, the local DBMSs may not be aware of each other, and, as a consequence, cannot coordinate their actions. Thus, traditional techniques for ensuring transaction atomicity and consistency in homogeneous distributed database systems may not be appropriate for an MDBS environment. The objective of this paper is to provide a brief review of the most current work in the area of multidatabase transaction management. We first define the problem and argue that the multidatabase research will become increasingly important in the coming years. We then outline basic research issues in multidatabase transaction management and review recent results in the area. We conclude the paper with a discussion of open problems and practical implications of this research.
CS-TR-92-1432
Report Number: CS-TR-92-1435
Institution: Stanford University, Department of Computer Science
Title: Lecture notes on approximation algorithms: Volume I
Author: Motwani, Rajeev
Date: October 1993
Abstract: These lecture notes are based on the course CS351 (Dept. of Computer Science, Stanford University) offered during the academic year 1991-92. The notes below correspond to the first half of the course. The second half consists of topics such as AL4X SNP. cliques, and colorings, as well as more specialized material covering topics such as geometric problems, Steiner trees and multicommodity flows. The second half is being revised to incorporate the implications of recent results in approximation algorithms and the complexity of approximation problems. Please let me know if you would like to be on the mailing list for the second half. Comments, criticisms and corrections are welcome, please send them by electronic mail to rajeev@cs.Stanford.edu.
CS-TR-92-1435
Report Number: CS-TR-92-1441
Institution: Stanford University, Department of Computer Science
Title: Motion planning in stereotaxic radiosurgery
Author: Schweikard, Achim
Author: Adler, John R.
Author: Latombe, Jean-Claude
Date: September 1992
Abstract: Stereotaxic radiosurgery is a procedure which uses a beam of radiation as an ablative surgical instrument to destroy brain tumors. The beam is produced by a linear accelerator which is moved by a jointed mechanism. Radiation is concentrated by crossfiring at the tumor from multiple directions and the amount of energy deposited in normal brain tissues is reduced. Because access to the tumor is obstructed along some directions by critical regions (e.g., brainstem, optic nerves) and most tumors are not shaped like spheres, planning the path of the beam is often difficult and time-consuming. This paper describes a computer-based planner developed to assist the surgeon generate a satisfactory path, given the spatial distribution of the brain tissues obtained with medical imaging. Experimental results with the implemented planner are presented, including a comparison with manually generated paths. According to these results, automatic planning significantly improves energy deposition. It can also shorten the overall treatment, hence reducing the patient's pain and allowing the radiosurgery equipment to be used for more patients. Stereotaxic radiosurgery is an example of so-called "bloodless surgery". Computer-based planning techniques are expected to facilitate further development of this safer, less painful, and more cost effective type of surgery.
CS-TR-92-1441
Report Number: CS-TR-92-1446
Institution: Stanford University, Department of Computer Science
Title: Independent updates and incremental agreement in replicated databases
Author: Ceri, Stefano
Author: Houtsma, Maurice A. W.
Author: Keller, Arthur M.
Author: Samarati, Pierangela
Date: October 1992
Abstract: Update propagation and transaction atomicity are major obstacles to the development of replicated databases. Many practical applications, such as automated teller machine (ATM) networks, flight reservation, and part inventory control, do not really require these properties. In this paper we present an approach for incrementally updating a distributed, replicated database without requiring multi-site atomic commit protocols. We prove that the mechanism is correct, as it asymptotically performs all the updates on all the copies. Our approach has two important characteristics: it is progressive, and non-blocking. Progressive means that the transaction's coordinator always commits, possibly together with a group of other sites. The update is later propagated asynchronously to the remaining sites. Non-blocking means that each site can take unilateral decisions at each step of the algorithm. Sites which cannot commit updates are brought to the same final state by means of a reconciliation mechanism. This mechanism uses the history logs, which are stored locally at each site, to bring sites to agreement. It requires a small auxiliary data structure, called reception vector, to keep track of the time until which the other sites are guaranteed to be up-to-date. Several optimizations to the basic mechanism are also discussed.
CS-TR-92-1446
Report Number: CS-TR-92-1452
Institution: Stanford University, Department of Computer Science
Title: Deadline assignment in a distributed soft real-time system
Author: Kao, Ben
Author: Garcia-Molina, Hector
Date: October 1992
Abstract: In a distributed environment, tasks often have processing demands on multiple different sites. A distributed task is usually divided up into several subtasks, each one to be executed at some site in order. In a real-time system, an overall deadline is usually specified by an application designer indicating when a distributed task is to be finished. However, the problem of how a global deadline is automatically translated to the deadline of each individual subtask has not been well studied. This paper examines (through simulations) four strategies for subtask deadline assignment in a distributed soft real-time environment.
CS-TR-92-1452
Report Number: CS-TR-93-1491
Institution: Stanford University, Department of Computer Science
Title: Subtask Deadline Assignment for Complex Distributed Soft Real-Time Tasks
Author: Kao, Ben
Author: Garcia-Molina, Hector
Date: October 1993
Abstract: Complex distributed tasks often involve parallel execution of subtasks at different nodes. To meet the deadline of a global task, all of its parallel subtasks have to be finished on time. Comparing to a local task (which involves execution at only one node), a global task may have a much harder time making its deadline because it is fairly likely that at least one of its subtasks run into an overloaded node. Another problem with complex distributed tasks occurs when a global task consists of a number of serially executing subtasks. In this case, we have the problem of dividing up the end-to-end deadline of the global task and assigning them to the intermediate subtasks. In this paper, we study both of these problems. Different algorithms for assigning deadlines to subtasks are presented and evaluated.
CS-TR-93-1491
Report Number: CS-TR-93-1494
Institution: Stanford University, Department of Computer Science
Title: Index Structures for Information Filtering Under the Vector Space Model
Author: Yan, Tak W.
Author: Garcia-Molina, Hector
Date: December 1993
Abstract: With the ever increasing volumes of information generation, users of information systems are facing an information overload. It is desirable to support information filtering as a complement to traditional retrieval mechanism. The number of users, and thus profiles (representing users' long-term interests), handled by an information filtering system is potentially huge, and the system has to process a constant stream of incoming information in a timely fashion. The efficiency of the filtering process is thus an important issue. In this paper, we study what data structures and algorithms can be used to efficiently perform large-scale information filtering under the vector space model, a retrieval model established as being effective. We apply the idea of the standard inverted index to index user profiles. We devise an alternative to the standard inverted index, in which we, instead of indexing every term in a profile, select only the significant ones to index. We evaluate their performance and show that the indexing methods require orders of magnitude fewer I/Os to process a document than when no index is used. We also show that the proposed alternative performs better in terms of I/O and CPU processing time in many cases.
CS-TR-93-1494
Report Number: CS-TR-93-1499
Institution: Stanford University, Department of Computer Science
Title: The Sandwich Theorem
Author: Knuth, Donald E.
Date: January 1994
Abstract: This report contains expository notes about a function vartheta(G) that is popularly known as the Lovasz number of a graph G. There are many ways to define vartheta(G), and the surprising variety of different characterizations indicates in itself that vartheta(G) should be interesting. But the most interesting property of vartheta(G) is probably the fact that it can be computed efficiently, although it lies "sandwiched" between other classic graph numbers whose computation is NP-hard. I have tried to make these notes self-contained so that they might serve as an elementary introduction to the growing literature on Lovasz's fascinating function.
CS-TR-93-1499
Report Number: CS-TR-94-1500
Institution: Stanford University, Department of Computer Science
Title: 1993 Publications Summary for the Stanford Database Group
Author: Siroker, Marianne
Date: January 1994
Abstract: This Technical Report contains the first page of papers written by members of the Stanford Database Group during 1993. Readers interested in the full papers can fetch electronic copies via FTP.
CS-TR-94-1500
Report Number: CS-TR-94-1501
Institution: Stanford University, Department of Comuputer Science
Title: Deriving Properties of Belief Update from Theories of Action
Author: Val, Alvaro del
Author: Shoham, Yoav
Date: February 1994
Abstract: We present an approach to database update as a form of non monotonic temporal reasoning, the main idea of which is the (circumscriptive) minimization of changes with respect to a set of facts declared ``persistent by default.'' The focus of the paper is on the relation between this approach and the update semantics recently proposed by Katsuno and Mendelzon. Our contribution in this regard is twofold: - We prove a representation theorem for KM semantics in terms of a restricted subfamily of the operators defined by our construction. - We show how the KM semantics can be generalized by relaxing our construction in a number of ways, each justified in certain intuitive circumstances and each corresponding to one specific postulate. It follows that there are reasonable update operators outside the KM family. Our approach is not dependent for its plausibility on this connection with KM semantics. Rather, it provides a relatively rich and flexible framework in which the frame and ramification problems can be solved in a systematic way by reasoning about default persistence of facts.
CS-TR-94-1501
Report Number: CS-TR-94-1502
Institution: Stanford University, Department of Computer Science
Title: Natural Language Parsing as Statistical Pattern Recognition
Author: Magerman, David M.
Date: February 1994
Abstract: Traditional natural language parsers are based on rewrite rule systems developed in an arduous, time-consuming manner by grammarians. A majority of the grammarian's efforts are devoted to the disambiguation process, first hypothesizing rules which dictate constituent categories and relationships among words in ambiguous sentences, and then seeking exceptions and corrections to these rules. In this work, I propose an automatic method for acquiring a statistical parser from a set of parsed sentences which takes advantage of some initial linguistic input, but avoids the pitfalls of the iterative and seemingly endless grammar development process. Based on distributionally-derived and linguistically-based features of language, this parser acquires a set of statistical decision trees which assign a probability distribution on the space of parse trees given the input sentence. By basing the disambiguation criteria selection on entropy reduction rather than human intuition, this parser development method is able to consider more sentences than a human grammarian can when making individual disambiguation rules. In experiments, the decision tree parser significantly outperforms a grammarian's rule-based parser, achieving an accuracy rate of 78% compared to the rule-based parser's 69%.
CS-TR-94-1502
Report Number: CS-TR-94-1503
Institution: Stanford University, Department of Computer Science
Title: Deciding whether to plan to react
Author: Dabija, Vlad G.
Date: February 1994
Abstract: Intelligent agents that operate in real-world real-time environments have limited resources. An agent must take these limitations into account when deciding which of two control modes - planning versus reaction - should control its behavior in a given situation. The main goal of this thesis is to develop a framework that allows a resource-bounded agent to decide at planning time which control mode to adopt for anticipated possible run-time contingencies. Using our framework, the agent: (a) analyzes a complete (conditional) plan for achieving a particular goal; (b) decides which of the anticipated contingencies require and allow for preparation of reactive responses at planning time; and (c) enhances the plan with prepared reactions for critical contingencies, while maintaining the size of the plan, the planning and response times, and the use of all other critical resources of the agent within task-specific limits. For a given contingency, the decision to plan or react is based on the characteristics of the contingency, the associated reactive response, and the situation itself. Contingencies that may occur in the same situation compete for reactive response preparation because of the agent's limited resources. The thesis also proposes a knowledge representation formalism to facilitate the acquisition and maintenance of knowledge involved in this decision process. We also show how the proposed framework can be adapted for the problem of deciding, for a given contingency, whether to prepare a special branch in the conditional plan under development or to leave the contingency for opportunistic treatment at execution time. We make a theoretical analysis of the properties of our framework and then demonstrate them experimentally. We also show experimentally that this framework can simulate several different styles of human reactive behaviors described in the literature and, therefore, can be useful as a basis for describing and contrasting such behaviors. Finally we demonstrate that the framework can be applied in a challenging real domain. That is: (a) the knowledge and data needed for the decision making within our framework exist and can be acquired from experts, and (b) the behavior of an agent that uses our framework improves according to response time, reliability and resource utilization criteria.
CS-TR-94-1503
Report Number: CS-TR-94-1504
Institution: Stanford University, Department of Computer Science
Title: An Algebraic Approach to Rule Analysis in Expert Database Systems
Author: Baralis, Elena
Author: Widom, Jennifer
Date: February 1994
Abstract: Expert database systems extend the functionality of conventional database systems by providing a facility for creating and automatically executing Condition-Action rules. While Condition-Action rules in database systems are very powerful, they also can be very difficult to program, due to the unstructured and unpredictable nature of rule processing. We provide methods for static analysis of Condition-Action rules; our methods determine whether a given rule set is guaranteed to terminate, and whether rule execution is confluent (has a guaranteed unique final state). Our methods are based on previous methods for analyzing rules in active database systems. We improve considerably on the previous methods by providing analysis criteria that are much less conservative: our methods often determine that a rule set will terminate or is confluent when previous methods could not. Our improved analysis is based on a ``propagation'' algorithm, which uses a formal approach based on an extended relational algebra to accurately determine when the action of one rule can affect the condition of another. Our algebraic approach yields methods that are applicable to a broad class of expert database rule languages.
CS-TR-94-1504
Report Number: CS-TR-94-1505
Institution: Stanford University, Department of Computer Science
Title: Using a Position History-Based Protocol for Distributed Object Visualization
Author: Singhal, Sandeep K.
Author: Cheriton, David R.
Date: February 1994
Abstract: Users of distributed virtual reality applications interact with users located across the network. Similarly, distributed object visualization systems store dynamic data at one host and render it in real-time at other hosts. Because data in both systems is animated and exhibits unpredictable behavior, providing up-to-date information about remote objects is expensive. Remote hosts must instead apply extrapolation between successive update packets to render the object's true animated behavior. This paper describes and analyzes a ``position history-based'' protocol in which hosts apply several recent position updates to track the position of remote objects. The history-based approach offers smooth, accurate visualizations of remote objects while providing a scalable solution.
CS-TR-94-1505
Report Number: CS-TR-94-1506
Institution: Stanford University, Department of Computer Science
Title: Optimized Memory-Based Messaging: Leveraging the Memory System for High-Performance Communication
Author: Cheriton, David R.
Author: Kutter, Robert A.
Date: February 1994
Abstract: Memory-based messaging, passing messages between programs using shared memory, is a recognized technique for efficient communication that takes advantage of memory system performance. However, the conventional operating system support for this approach is inefficient, especially for large-scale multiprocessor interconnects, and is too complex to effectively support in hardware. This paper describes hardware and software optimizations for memory-based messaging that efficiently exploit the mechanisms of the memory system to provide superior communication performance. We describe the overall model of optimized memory-based messaging, its implementation in an operating system kernel and hardware support for this approach in a scalable multiprocessor architecture. The optimizations include address-valued signals, message-oriented memory consistency and automatic signaling on write. Performance evaluations show these extensions provide a three-to-five-fold improvement in communication performance over a comparable software-only implementation.
CS-TR-94-1506
Report Number: CS-TR-94-1507
Institution: Stanford University, Department of Computer Science
Title: Bibliography Department of Computer Science Technical Reports, 1963-1993
Author: Mashack, Thea
Date: March 1994
Abstract: This Bibliography lists all the reports published by the Department of Computer Science from 1963 through 1993
CS-TR-94-1507
Report Number: CS-TR-94-1508
Institution: Stanford University, Department of Computer Science
Title: Inverse Kinematics of a Human Arm
Author: Kondo, Koichi
Date: March 1994
Abstract: This paper describes a new inverse kinematics algorithm for a human arm. Potential applications of this algorithm include computer-aided design and concurrent engineering from the viewpoint of human factors. For example, it may be used to evaluate a new design in terms of its usability and to automatically generate instruction videos. The inverse kinematics algorithm is based on a sensorimotor transformation model developed in recent neurophysiological experiments. This method can be applied to both static arm postures and human manipulation motions.
CS-TR-94-1508
Report Number: CS-TR-94-1509
Institution: Stanford University, Department of Computer Science
Title: Global Price Updates Help
Author: Goldberg, Andrew V.
Author: Kennedy, Robert
Date: March 1994
Abstract: Periodic global updates of dual variables have been shown to yield a substantial speed advantage in implementations of push-relabel algorithms for the maximum flow and minimum cost flow problems. In this paper, we show that in the context of the bipartite matching and assignment problems, global updates yield a theoretical improvement as well. For bipartite matching, a push-relabel algorithm that matches the best bound when global updates are used achieves a bound that is worse by a square root of n factor without the updates. A similar result holds for the assignment problem.
CS-TR-94-1509
Report Number: CS-TR-94-1510
Institution: Stanford University, Department of Computer Science
Title: Key Objects in Garbage Collection
Author: Hayes, Barry
Date: March 1994
Abstract: When the cost of global garbage collection in a system grows large, the system can be redesigned to use generational collection. The newly-created objects usually have a much shorter half-life than average, and by concentrating the collector's efforts on them a large fraction of the garbage can be collected at a tiny fraction of the cost. The objects that survive generational collection may still become garbage, and the current practice is to perform occasional global garbage collections to purge these objects from the system, and again, the cost of doing these collections may become prohibitive when the volume of memory increases. Previous research has noted that the objects that survive generational collection often are born, promoted, and collected in large clusters. In this dissertation I show that carefully selected semantically or structurally important key objects can be drawn from the clusters and collected separately; when a key object becomes unreachable, the collector can take this as a hint to collect the cluster from which the key was drawn. To gauge the effectiveness of key objects, their use was simulated in ParcPlace's Objectworks\Smalltalk system. The objects selected as keys were those that, as young objects, had pointers to them stored into old objects. The collector attempts to create a cluster for each key by gathering together all of the objects reachable from that key and >From no previous key. Using this simple heuristic for key objects, the collector finds between 41% and 92% of the clustered garbage in a suite of simple test programs. Except for one program in the suite, about 95% of the time these key objects direct the collector to a cluster that is garbage. The exception should be heeded in improving the heuristics. In a replay of an interactive session, key object collection finds 59% of the clustered garbage and 66% of suggested targets are indeed garbage.
CS-TR-94-1510
Report Number: CS-TR-94-1511
Institution: Stanford University, Department of Computer Science
Title: Co-Learning and the Evolution of Social Acitivity
Author: Shoham, Yoav
Author: Tennenholtz, Moshe
Date: April 1994
Abstract: We introduce the notion of co-learning, which refers to a process in which several agents simultaneously try to adapt to one another's behavior so as to produce desirable global system properties. Of particular interest are two specific co-learning settings, which relate to the emergence of conventions and the evolution of cooperation in societies, respectively. We define a basic co-learning rule, called Highest Cumulative Reward (HCR), and show that it gives rise to quite nontrivial system dynamics. In general, we are interested in the eventual convergence of the co-learning system to desirable states, as well as in the efficiency with which this convergence is attained. Our results on eventual convergence are analytic; the results on efficiency properties include analytic lower bounds as well as empirical upper bounds derived from rigorous computer simulations.
CS-TR-94-1511
Report Number: CS-TR-94-1512
Institution: Stanford University, Department of Computer Science
Title: Abstraction Planning in Real Time
Author: Washington, Richard
Date: April 1994
Abstract: When a planning agent works in a complex, real-world domain, it is unable to plan for and store all possible contingencies and problem situations ahead of time. The agent needs to be able to fall back on an ability to construct plans at run time under time constraints. This thesis presents a method for planning at run time that incrementally builds up plans at multiple levels of abstraction. The plans are continually updated by information from the world, allowing the planner to adjust its plan to a changing world during the planning process. All the information is represented over intervals of time, allowing the planner to reason about durations, deadlines, and delays within its plan. In addition to the method, the thesis presents a formal model of the planning process and uses the model to investigate planning strategies. The method has been implemented, and experiments have been run to validate the overall approach and the theoretical model.
CS-TR-94-1512
Report Number: CS-TR-94-1513
Institution: Stanford University, Department of Computer Science
Title: Construction of Normative Decision Models Using Abstract Graph Grammars
Author: Egar, John W.
Date: May 1994
Abstract: This dissertation addresses automated assistance for decision analysis in medicine. In particular, I have investigated graph grammars as a representation for encoding how decision-theoretic models can be constructed from an unordered list of concerns. The modeling system that I have used requires a standard vocabulary to generate decision models; the models generated are qualitative, and require subsequent assessment of probabilities and utility values. This research has focused on the modeling of the qualitative structure of problems given a standard vocabulary and given that subsequent assessment of probabilities and utilities is possible. The usefulness of the graph-grammar representation depends on the graph-grammar formalism's ability to describe a broad spectrum of qualitative decision models, on its ability to maintain a high quality in the models it generates, and on its clarity in describing topological constraints to researchers who design and maintain the actual grammar. I have found that graph grammars can be used to generate automatically decision models that are comparable to those produced by decision analysts.
CS-TR-94-1513
Report Number: CS-TR-94-1514
Institution: Stanford University, Department of Computer Science
Title: Load Balancing Using Time Series Analysis for Soft Real Time Systems with Statistically Periodic Loads
Author: Hailperin, Max
Date: May 1994
Abstract: This thesis provides design and analysis of techniques for global load balancing on ensemble architectures running soft-real-time object-oriented applications with statistically periodic loads. It focuses on estimating the instantaneous average load over all the processing elements. The major contribution is the use of explicit stochastic process models for both the loading and the averaging itself. These models are exploited via statistical time-series analysis and Bayesian inference to provide improved average load estimates, and thus to facilitate global load balancing. This thesis explains the distributed algorithms used and provides some optimality results. It also describes the algorithms' implementation and gives performance results from simulation. These results show that our techniques allow more accurate estimation of the global system loading, resulting in fewer object migrations than local methods. Our method is shown to provide superior performance, relative not only to static load-balancing schemes but also to many adaptive load-balancing methods. Results from a preliminary analysis of another system and from simulation with a synthetic load provide some evidence of more general applicability.
CS-TR-94-1514
Report Number: CS-TR-94-1515
Institution: Stanford University, Department of Computer Science
Title: Retrieving Semantically Distant Analogies
Author: Wolverton, Michael
Date: June 1994
Abstract: Techniques that have traditionally been useful for retrieving same-domain analogies from small single-use knowledge bases, such as spreading activation and indexing on selected features, are inadequate for retrieving cross-domain analogies from large multi-use knowledge bases. Blind or near-blind search techniques like spreading activation will be overwhelmed by combinatorial explosion as the search goes deeper into the KB. And indexing a large multi-use KB on salient features is impractical, largely because a feature that may be useful for retrieval in one task may be useless for another task. This thesis describes Knowledge-Directed Spreading Activation (KDSA), a method for retrieving analogies in a large semantic network. KDSA uses task-specific knowledge to guide a spreading activation search to a case or concept in memory that meets a desired similarity condition. The thesis also describes a specific instantiation of this method for the task of innovative design. KDSA has been validated in two ways. First, a theoretical model of knowledge base search demonstrates that KDSA is tractable for retrieving semantically distant analogies under a wide range of knowledge base configurations. Second, an implemented system that uses KDSA to find analogies for innovative design shows that the method is able to retrieve semantically distant analogies for a real task. Experiments with that system show trends as the knowledge base size grows that suggest the theoretical model's prediction of large knowledge base tractability is accurate.
CS-TR-94-1515
Report Number: CS-TR-94-1516
Institution: Stanford University, Department of Computer Science
Title: A Framework for Reasoning Precisely with Vague Concepts
Author: Goyal, Nita
Date: May 1994
Abstract: Many knowledge-based systems need to represent vague concepts such as ``old'' and ``tall''. The practical approach of representing vague concepts as precise intervals over numbers (e.g., ``old'' as the interval [70,110]) is well-accepted in Artificial Intelligence. However, there have been no systematic procedures, but only ad hoc methods to delimit the boundaries of intervals representing the vague predicates. A key observation is that the vague concepts and their interval boundaries are constrained by the underlying domain knowledge. Therefore, any systematic approach to assigning interval boundaries must take the domain knowledge into account. Hence, in the dissertation, we present a framework to represent the domain knowledge and exploit it to reason about the interval boundaries via a query language. This framework is comprised of a constraint language to represent logical constraints on vague concepts, as well as numerical constraints on the interval boundaries; a query language to request information about the interval boundaries; and an algorithm to answer the queries. The algorithm preprocesses the constraints by extracting the numerical information from the logical constraints and combines them with the given numerical constraints. We have implemented the framework and applied it to medical domain to illustrate its usefulness.
CS-TR-94-1516
Report Number: CS-TR-94-1517
Institution: Stanford University, Department of Computer Science
Title: Reactive, Generative and Stratified Models of Probabilistic Processes
Author: Glabbeek, Rob J. van
Author: Smolka, Scott A.
Author: Steffen, Bernhard
Date: July 1994
Abstract: We introduce three models of probabilistic processes, namely, reactive, generative and stratified. These models are investigated within the context of PCCS, an extension of Milner's SCCS in which each summand of a process summation expression is guarded by a probability and the sum of these probabilities is 1. For each model we present a structural operational semantics of PCCS and a notion of bisimulation equivalence which we prove to be a congruence. We also show that the models form a hierarchy: the reactive model is derivable from the generative model by abstraction from the relative probabilities of different actions, and the generative model is derivable from the stratified model by abstraction from the purely probabilistic branching structure. Moreover the classical nonprobabilistic model is derivable from each of these models by abstraction from all probabilities.
CS-TR-94-1517
Report Number: CS-TR-94-1518
Institution: Stanford University, Department of Computer Science
Title: STeP: The Stanford Temporal Prover
Author: Manna, Z ohar
Author: Anuchitanukul, Anuchit
Author: Bjorner, Nikolaj
Author: Browne, Anca
Author: Chang, Edward
Author: Colon, Michael
Author: de Alfaro, Luca
Author: Devarajan, Harish
Author: Sipma, Henny
Author: Uribe, Tomas
Date: June 1994
Abstract: We describe the Stanford Temporal Prover (STeP), a system being developed to support the computer-aided formal verification of concurrent and reactive systems based on temporal specifications. Unlike systems based on model-checking, STeP is not restricted to finite-state systems. It combines model checking and deductive methods to allow the verification of a broad class of systems, including programs with infinite data domains, N-process programs, and N-component circuit designs, for arbitrary N. In short, STeP has been designed with the objective of combining the expressiveness of deductive methods with the simplicity of model checking. The verification process is for the most part automatic. User interaction occurs mostly at the highest, most intuitive level, primarily through a graphical proof language of verification diagrams. Efficient simplification methods, decision procedures, and invariant generation techniques are then invoked automatically to prove resulting first-order verification conditions with minimal assistance. We describe the performance of the system when applied to several examples, including the N-process dining philosopher's program, Szymanski's N-process mutual exclusion algorithm, and a distributed N-way arbiter circuit.
CS-TR-94-1518
Report Number: CS-TR-94-1519
Institution: Stanford University, Department of Computer Science
Title: Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces
Author: Kavraki, Lydia
Author: Svestka, Petr
Author: Latombe, Jean-Claude
Author: Overmars, Mark
Date: August 1994
Abstract: A new motion planning method for robots in static workspaces is presented. This method proceeds according to two phases: a learning phase and a query phase. In the learning phase, a probabilistic roadmap is constructed and stored as a graph whose nodes correspond to collision-free configurations and edges to feasible paths between these configurations. These paths are computed using a simple and fast local planner. In the query phase, any given start and goal configurations of the robot are connected to two nodes of the roadmap; the roadmap is then searched for a path joining these two nodes. The method is general and easy to implement. It can be applied to virtually any type of holonomic robot. It requires selecting certain parameters (e.g., the duration of the learning phase) whose values depend on the considered scenes, that is the robots and their workspaces. But these values turn out to be relatively easy to choose. Increased efficiency can also be achieved by tailoring some components of the method (e.g., the local planner) to the considered robots. In this paper the method is applied to planar articulated robots with many degrees of freedom. Experimental results show that path planning can be done in a fraction of a second on a contemporary workstation (approximately 150 MIPS), after learning for relatively short periods of time (a few dozen seconds).
CS-TR-94-1519
Report Number: CS-TR-94-1520
Institution: Stanford University, Department of Computer Science
Title: Adaptive Optimization for SELF: Reconciling High Performance with Exploratory Programming
Author: Holzle, Urs
Date: August 1994
Abstract: Crossing abstraction boundaries often incurs a substantial run-time overhead in the form of frequent procedure calls. Thus, pervasive use of abstraction, while desirable from a design standpoint, may lead to very inefficient programs. Aggressively optimizing compilers can reduce this overhead but conflict with interactive programming environments because they introduce long compilation pauses and often preclude source-level debugging. Thus, programmers are caught on the horns of two dilemmas: they have to choose between abstraction and efficiency, and between responsive programming environments and efficiency. This dissertation shows how to reconcile these seemingly contradictory goals. Four new techniques work together to achieve this: - Type feedback achieves high performance by allowing the compiler to inline message sends based on information extracted from the runtime system. - Adaptive optimization achieves high responsiveness without sacrificing performance by using a fast compiler to generate initial code while automatically recompiling heavily used program parts with an optimizing compiler. - Dynamic deoptimization allows source-level debugging of optimized code by transparently recreating non-optimized code as needed. - Polymorphic inline caching speeds up message dispatch and, more significantly, collects concrete type information for the compiler. With better performance yet good interactive behavior, these techniques reconcile exploratory programming, ubiquitous abstraction, and high performance.
CS-TR-94-1520
Report Number: CS-TR-94-1521
Institution: Stanford University, Department of Computer Science
Title: Chu Spaces : A Model for Concurrency
Author: Gupta, Vineet
Date: August 1994
Abstract: A Chu space is a binary relation between two sets. In this thesis we show that Chu spaces form a non-interleaving model of concurrency which extends event structures while endowing them with an algebraic structure whose natural logic is linear logic. We provide several equivalent definitions of Chu spaces, including two pictorial representations. Chu spaces represent processes as automata or schedules, and Chu duality gives a simple way of converting between schedules and automata. We show that Chu spaces can represent various concurrency concepts like conflict, temporal precedence and internal and external choice, and they distinguish between causing and enabling events. We present a process algebra for Chu spaces including the standard combinators like parallel composition, sequential composition, choice, interaction, restriction, and show that the various operational identities between these hold for Chu spaces. The solution of recursive domain equations is possible for most of these operations, giving us an expressive specification and programming language. We define a history preserving equivalence between Chu spaces, and show that it preserves the causal structure of a process.
CS-TR-94-1521
Report Number: CS-TR-94-1522
Institution: Stanford University, Department of Computer Science
Title: Compositional Verification of Reactive and Real-time Systems
Author: Chang, Edward
Date: December 1993
Abstract: This thesis presents a compositional methodology for the verification of reactive and real-time systems. The correctness of a given system is established from the correctness of the system's components, each of which may be treated as a system itself and further reduced. When no further reduction is possible or desirable, global techniques for verification may be used to verify the bottom-level components. Transition modules are introduced as a suitable compositional model of computation. Various composition operations are defined on transition modules, including parallel composition, sequential composition, and iteration. A restricted assumption-guarantee style of specification is advocated, wherein the environment assumption is stated as a restriction on the environment's next-state relation. Compositional proof rules are provided in accordance with the safety-progress hierarchy of temporal properties. The compositional framework is then extended naturally to real-time transition modules and discrete-time metric temporal logic.
CS-TR-94-1522
Report Number: CS-TR-94-1523
Institution: Stanford University, Department of Computer Science
Title: On Implementing Push-Relabel Method for the Maximum Flow Problem
Author: Cherkassky, Boris V.
Author: Goldberg, Andrew V.
Date: September 1994
Abstract: We study efficient implementations of the push-relabel method for the maximum flow problem. The resulting codes are faster than the previous codes, and much faster on some problem families. The speedup is due to the combination of heuristics used in our implementation. We also exhibit a family of problems for which all known methods seem to have almost quadratic time growth rate.
CS-TR-94-1523
Report Number: CS-TR-94-1524
Institution: Stanford University, Department of Computer Science
Title: Continuous Verification by Discrete Reasoning
Author: de Alfaro, Luca
Author: Manna, Z ohar
Date: September 1994
Abstract: Two semantics are commonly used for the behavior of real-time and hybrid systems: a discrete semantics, in which the temporal evolution is represented as a sequence of snapshots describing the state of the system at certain times, and a continuous semantics, in which the temporal evolution is represented by a series of time intervals, and therefore corresponds more closely to the physical reality. Powerful verification rules are known for temporal logic formulas based on the discrete semantics. This paper shows how to transfer the verification techniques of the discrete semantics to the continuous one. We show that if a temporal logic formula has the property of finite variability, its validity in the discrete semantics implies its validity in the continuous one. This leads to a verification method based on three components: verification rules for the discrete semantics, axioms about time, and some temporal reasoning to bring the results together. This approach enables the verification of properties of real-time and hybrid systems with respect to the continuous semantics.
CS-TR-94-1524
Report Number: CS-TR-94-1525
Institution: Stanford University, Department of Computer Science
Title: Differential BDDs
Author: Anuchitanukul, Anuchit
Author: Manna, Z ohar
Date: September 1994
Abstract: In this paper, we introduce a class of Binary Decision Diagrams (BDDs) which we call Differential BDDs (DBDDs), and two transformations over DBDDs, called Push-up and Delta transformations. In DBDDs and its derived classes such as Push-up DBDDs or Delta DBDDs, in addition to the ordinary node-sharing in the normal Ordered Binary Decision Diagrams (OBDDs), some isomorphic substructures are collapsed together forming an even more compact representation of boolean functions. The elimination of isomorphic substructures coincides with the repetitive occurrences of the same or similar small components in many applications of BDDs such as in the representation of hardware circuits. The reduction in the number of nodes, from OBDDs to DBDDs, is potentially exponential while boolean manipulations on DBDDs remain efficient.
CS-TR-94-1525
Report Number: CS-TR-94-1526
Institution: Stanford University, Department of Computer Science
Title: Combining Experiential and Theoretical Knowledge in the Domain of Semiconductor Manufacturing
Author: Mohammed, John Llewelyn
Date: September 1994
Abstract: Semiconductor Manufacturing is characterized by complexity and continual, rapid change. These characteristics reduce the effectiveness of traditional diagnostic expert systems: the knowledge represented cannot adapt to changes in the manufacturing plan because the dependence of the knowledge on the plan is not explicitly represented. It is impractical to manually encode all the dependencies in a complex plan. We address this problem in two ways. First, we employ model-based techniques to encode theoretical knowledge, so that symbolic simulation of a new manufacturing plan can automatically glean diagnostic information. Our representation is sufficiently detailed to capture the plan's inherent causal dependencies, yet sufficiently abstract to make symbolic simulation practical. This theoretical knowledge can adapt to changes in the manufacturing plan. However, the expressiveness and tractability of our representational machinery limit the range of phenomena that we can represent. Second, we describe Generic Rules, which combine the expressiveness of heuristic rules with the robustness of theoretical models. Generic Rules are general patterns for heuristic rules, associated with model-based restrictions on the situations in which the patterns can be instantiated to form rules for new contexts. In this way, theoretical knowledge is employed to encode the dependence of heuristic knowledge on the manufacturing plan.
CS-TR-94-1526
Report Number: CS-TR-94-1527
Institution: Stanford University, Department of Computer Science
Title: From Knowledge to Belief
Author: Koller, Daphne
Date: October 1994
Abstract: When acting in the real world, an intelligent agent must make decisions under uncertainty. The standard solution requires it to assign degrees of belief to the relevant assertions. These should be based on the agent's knowledge. For example, a doctor deciding on the treatment for a patient should use information about that patient, statistical correlations between symptoms and diseases, default rules, and more. The random-worlds method induces degrees of belief from very rich knowledge bases, expressed in a language that augments first-order logic with statistical statements and default rules (interpreted as qualitative statistics). The method is based on the principle of indifference, treating all possible worlds as equally likely. It naturally derives important patterns of reasoning such as specificity, inheritance, indifference to irrelevant information, and a default assumption of independence. Its expressive power and intuitive semantics allow it to deal well with examples that are too complex for most other reasoning systems. We use techniques from finite model theory to analyze the computational aspects of random worlds. The problem of computing degrees of belief is undecidable in general. However, for unary knowledge bases, a tight connection to the principle of maximum entropy often allows us to compute degrees of belief.
CS-TR-94-1527
Report Number: CS-TR-94-1528
Institution: Stanford University, Department of Computer Science
Title: Architecture-Altering Operations for Evolving the Architecture of a Multi-Part Program in Genetic Programming
Author: Koza, John R.
Date: October 1994
Abstract: Previous work described a way to evolutionarily select the architecture of a multi-part computer program >From among preexisting alternatives in the population while concurrently solving a problem during a run of genetic programming. This report describes six new architecture-altering operations that provide a way to evolve the architecture of a multi-part program in the sense of actually changing the architecture of programs dynamically during the run. The new architecture-altering operations are motivated by the naturally occurring operation of gene duplication as described in Susumu Ohno's provocative 1970 book Evolution by Means of Gene Duplication as well as the naturally occurring operation of gene deletion. The six new architecture-altering operations are branch duplication, argument duplication, branch creation, argument creation, branch deletion and argument deletion. A connection is made between genetic programming and other techniques of automated problem solving by interpreting the architecture-altering operations as providing an automated way to specialize and generalize programs. The report demonstrates that a hierarchical architecture can be evolved to solve an illustrative symbolic regression problem using the architecture- altering operations. Future work will study the amount of additional computational effort required to employ the architecture-altering operations.
CS-TR-94-1528
Report Number: CS-TR-94-1529
Institution: Stanford University, Department of Computer Science
Title: A knowledge-based method for temporal abstraction of clinical data
Author: Shahar, Yuval
Date: October 1994
Abstract: This dissertation describes a domain-independent method specific to the task of abstracting higher-level concepts from time-stamped data. The framework includes a model of time, parameters, events and contexts. I applied my framework to several domains of medicine. My goal is to create, from time-stamped patient data, interval-based temporal abstractions such as "severe anemia for 3 weeks in the context of administering AZ T." The knowledge-based temporal-abstraction method decomposes the task of abstracting higher-level abstractions from input data into five subtasks. These subtasks are solved by five domain-independent temporal-abstraction mechanisms. The temporal-abstraction mechanisms depend on four domain-specific knowledge types. I implemented the knowledge-based temporal-abstraction method in the RESUME system. RESUME accepts input and returns output at all levels of abstraction; accepts input out of temporal order, modifying a view of the past or of the present, as necessary; generates context-sensitive, controlled output; and maintains several possible concurrent interpretations of the data. I evaluated RESUME in the domains of protocol-based care, monitoring of children's growth, and therapy of diabetes. A formal specification of a domain's temporal-abstraction knowledge supports acquisition, maintenance, reuse, and sharing of that knowledge.
CS-TR-94-1529
Report Number: CS-TR-94-1530
Institution: Stanford University, Department of Computer Science
Title: On Computing Multi-Arm Manipulation Trajectories
Author: Koga, Yoshihito
Date: October 1994
Abstract: This dissertation considers the manipulation task planning problem of automatically generating the trajectories for several cooperating robot arms to manipulate a movable object to a goal location among obstacles. The planner must reason that the robots may need to change their grasp of the object to complete the task, for example, by passing it from one arm to another. Furthermore, the computed velocities and accelerations of the arms must satisfy the limits of the actuators. Past work strongly suggests that solving this problem in a rigorous fashion is intractable. We address this problem in a practical two-phase approach. In step one, using a heuristic we compute a collision-free path for the robots and the movable object. For the case of multiple robot arms with many degrees of freedom, this step may fail to find the desired path even though it exists. Despite this limitation, experimental results of the implemented planner (for solving step one) show that it is efficient and reliable; for example, the planner is able to find complex manipulation motions for a system with seventy eight degrees of freedom. In step two, we then find the time-parameterization of the path such that the dynamic constraints on the robot are satisfied. In fact, we find the time-optimal solution for the given path. We show simulation results for various complex examples.
CS-TR-94-1530
Report Number: CS-TR-94-1531
Institution: Stanford University, Department of Computer Science
Title: On-Line Manipulation Planning for Two Robot Arms in a Dynamic Environment
Author: Li, Tsai-Yen
Author: Latombe, Jean-Claude
Date: December 1994
Abstract: In a constantly changing and partially unpredictable environment, robot motion planning must be on-line. The planner receives a continuous flow of information about occurring events and generates new plans, while previously planned motions are being executed. This paper describes an on-line planner for two cooperating arms whose task is to grab parts of various types on a conveyor belt and transfer them to their respective goals while avoiding collision with o