ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 35 Issue 1, Jan. 1988

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...