**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*(n^{2}(m + *N*log *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...