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 2, April 1988

On the shortest paths between two convex polyhedra
Avikam Balstan, Micha Sharir
Pages: 267-287
DOI: 10.1145/42282.214094
The problem of computing the Euclidean shortest path between two points in three-dimensional space bounded by a collection of convex and disjoint polyhedral obstacles having n faces altogether is considered. This problem is...

Consensus in the presence of partial synchrony
Cynthia Dwork, Nancy Lynch, Larry Stockmeyer
Pages: 288-323
DOI: 10.1145/42282.42283
The concept of partial synchrony in a distributed system is introduced. Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper bound &Dgr; on the time...

Church-Rosser Thue systems and formal languages
Robert McNaughton, Paliath Narendran, Friedrich Otto
Pages: 324-344
DOI: 10.1145/42282.42284
Since about 1971, much research has been done on Thue systems that have properties that ensure viable and efficient computation. The strongest of these is the Church-Rosser property, which states that two equivalent strings can each be brought...

Efficient tests for top-down termination of logical rules
Jeffrey D. Ullman, Allen Van Gelder
Pages: 345-373
DOI: 10.1145/42282.42285
Considered is the question of whether top-down (Prolog-like) evaluation of a set of logical rules can be guaranteed to terminate. The NAIL! system is designed to process programs consisting of logical rules and to select, for each fragment of...

An O(n2(m + Nlog n)log n) min-cost flow algorithm
Zvi Galil, Éva Tardos
Pages: 374-386
DOI: 10.1145/42282.214090
The minimum-cost flow problem is: Given a network with n vertices and m edges, find a maximum flow of minimum cost. Many network problems are easily reducible to this problem. A polynomial-time algorithm for the...

The time complexity of maximum matching by simulated annealing
Galen H. Sasaki, Bruce Hajek
Pages: 387-403
DOI: 10.1145/42282.46160
The random, heuristic search algorithm called simulated annealing is considered for the problem of finding the maximum cardinality matching in a graph. It is shown that neither a basic form of the algorithm, nor any other algorithm in a fairly...

The schematic protection model: its definition and analysis for acyclic attenuating schemes
Ravinderpal Singh Sandhu
Pages: 404-432
DOI: 10.1145/42282.42286
The protection state of a system is defined by the privileges possessed by subjects at a given moment. Operations that change this state are themselves authorized by the current state. This poses a design problem in constructing the initial...

Optimal directory placement on disk storage devices
A. R. Calderbank, E. G. Coffman, Jr., Leopold Flatto
Pages: 433-446
DOI: 10.1145/42282.42287
Two mathematical models dealing with optimal placement of directories on disk devices are analyzed. Storage addresses on the disk are approximated by points in the interval [0, 1]. Requests for information on the disk are represented by a...

Comparing the combinational complexities of arithmetic functions
Helmut Alt
Pages: 447-460
DOI: 10.1145/42282.214084
Methods are presented for finding reductions between the computations of certain arithmetic functions that preserve asymptotic Boolean complexities (circuit depth or size). They can be used to show, for example, that all nonlinear algebraic...

On the complexity of branching programs and decision trees for clique functions
Ingo Wegener
Pages: 461-471
DOI: 10.1145/42282.46161
Exponential lower bounds on the complexity of computing the clique functions in the Boolean decision-tree model are proved. For one-time-only branching programs, large polynomial lower bounds are proved for k-clique functions if...