**Many-sorted unification**

Christoph Walther

Pages: 1-17

DOI: 10.1145/42267.45071

Many-sorted unification is considered; that is, unification in the many-sorted free algebras of terms, where variables, as well as the domains and ranges of functions, are restricted to certain subsets of the universe, given as a potentially...

**The complexity of searching a graph**

N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, C. H. Papadimitriou

Pages: 18-44

DOI: 10.1145/42267.42268

T. Parsons originally proposed and studied the following pursuit-evasion problem on graphs: Members of a team of searchers traverse the edges of a graph G in pursuit of a fugitive, who moves along the edges of the graph with...

**Optimal design and use of retry in fault-tolerant computer systems**

Yann-Heng Lee, Kang G. Shin

Pages: 45-69

DOI: 10.1145/42267.42269

In this paper, a new method is presented for (i) determining an optimal retry policy and (ii) using retry for fault characterization, which is defined as classification of the fault type and determination of...

**Equivalence and optimization of relational transactions**

Serge Abiteboul, Victor Vianu

Pages: 70-120

DOI: 10.1145/42267.42271

A large class of relational database update transactions is investigated with respect to equivalence and optimization. The transactions are straight-line programs with inserts, deletes, and modifications using simple selection conditions....

**A theory of reliability in database systems**

Vassos Hadzilacos

Pages: 121-145

DOI: 10.1145/42267.42272

Reliable concurrent processing of transactions in a database system is examined. Since serializability, the conventional concurrency control correctness criterion, is not adequate in the presence of common failures, another theory of correctness...

**On conjunctive queries containing inequalities**

Anthony Klug

Pages: 146-160

DOI: 10.1145/42267.42273

Conjunctive queries are generalized so that inequality comparisons can be made between elements of the query. Algorithms for containment and equivalence of such “inequality queries” are given, under the assumption that the data...

**External hashing with limited internal storage**

Gaston H. Gonnet, Per-Åke Larson

Pages: 161-184

DOI: 10.1145/42267.42274

The following problem is studied: How, and to what extent, can the retrieval speed of external hashing be improved by storing a small amount of extra information in internal storage? Several algorithms that guarantee retrieval in one access are...

**Automating program analysis**

Timothy Hickey, Jacques Cohen

Pages: 185-220

DOI: 10.1145/42267.42275

The first part of the paper shows that previous theoretical work on the semantics of probabilistic programs (Kozen) and on the correctness of performance annotated programs (Ramshaw) can be used to automate the average-case analysis of simple...

**A vertex-allocation theorem for resources in queuing networks**

Satish K. Tripathi, C. Murray Woodside

Pages: 221-230

DOI: 10.1145/42267.45068

A product-form queuing network with multiple open and closed chains is considered. Some of the closed chains, which have a single customer each, require allocation of resources in the network so as to maximize a weighted throughput performance...

**Greatest common divisors of polynomials given by straight-line programs**

Erich Kaltofen

Pages: 231-264

DOI: 10.1145/42267.45069

Algorithms on multivariate polynomials represented by straight-line programs are developed. First, it is shown that most algebraic algorithms can be probabilistically applied to data that are given by a straight-line computation. Testing such...