#### Journal of the ACM (JACM), Volume 47 Issue 1, Jan. 2000

**The harmonic k-server algorithm is competitive**

Yair Bartal, Eddie Grove

Pages: 1-15

DOI: 10.1145/331605.331606

The k-server problem is a generalization of the paging problems, and is the most studied problem in the area of competive online problems. The Harmonic algorithm is a very natural and simple randomized algorithm for the...

**Parallel RAMs with owned global memory and deterministic context-free language recognition**

Patrick W. Dymond, Walter L. Ruzzo

Pages: 16-45

DOI: 10.1145/331605.331607

We identify and study a natural and frequently occurring subclass of Concurrent Read, Exclusive Write Parallel Random Access Machines (CREW-PRAMs). Called Concurrent Read, Owner Write, or CROW-PRAMS, these are machines in which...

**Minimum cuts in near-linear time**

David R. Karger

Pages: 46-76

DOI: 10.1145/331605.331608

We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling...

**Existential second-order logic over strings**

Thomas Eiter, Georg Gottlob, Yuri Gurevich

Pages: 77-131

DOI: 10.1145/331605.331609

Existential second-order logic (ESO) and monadic second-order logic(MSO) have attracted much interest in logic and computer science. ESO is a much expressive logic over successor structures than MSO. However, little was known about the...

**Polylog-time and near-linear work approximation scheme for undirected shortest paths**

Edith Cohen

Pages: 132-166

DOI: 10.1145/331605.331610

Shortest paths computations constitute one of the most fundamental network problems. Nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than...

**From Algol to polymorphic linear lambda-calculus**

Peter W. O'Hearn, John C. Reynolds

Pages: 167-223

DOI: 10.1145/331605.331611

In a linearly-typed functional language, one can define functions that consume their arguments in the process of computing their results. This is reminiscent of state transformations in imperative languages, where execition of an assignment...