Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 35 Issue 3, July 1988

A mechanical proof of the Church-Rosser theorem
N. Shankar
Pages: 475-522
DOI: 10.1145/44483.44484
The Church-Rosser theorem is a celebrated metamathematical result on the lambda calculus. We describe a formalization and proof of the Church-Rosser theorem that was carried out with the Boyer-Moore theorem prover. The proof presented in this...

Finding a maximum-genus graph imbedding
Merrick L. Furst, Jonathan L. Gross, Lyle A. McGeoch
Pages: 523-534
DOI: 10.1145/44483.44485
The computational complexity of constructing the imbeddings of a given graph into surfaces of different genus is not well understood. In this paper, topological methods and a reduction to linear matroid parity are used to develop a...

The coloring and maximum independent set problems on planar perfect graphs
Wen-Lian Hsu
Pages: 535-563
DOI: 10.1145/44483.44486
Efficient decomposition algorithms for the weighted maximum independent set, minimum coloring, and minimum clique cover problems on planar perfect graphs are presented. These planar graphs can also be characterized by the absence of induced odd...

Some distributions that allow perfect packing
Wansoo T. Rhee, Michel Talagrand
Pages: 564-578
DOI: 10.1145/44483.44487
A probability distribution &mgr; on [0, 1] allows perfect packing if n items of size X1, … , Xn, independent...

Stability of binary exponential backoff
Jonathan Goodman, Albert G. Greenberg, Neal Madras, Peter March
Pages: 579-602
DOI: 10.1145/44483.44488
Binary exponential backoff is a randomized protocol for regulating transmissions on a multiple-access broadcast channel. Ethernet, a local-area network, is built upon this protocol. The fundamental theoretical issue is stability: Does the...

The physical mapping problem for parallel architectures
Lenwood S. Heath, Arnold L. Rosenberg, Bruce T. Smith
Pages: 603-634
DOI: 10.1145/44483.44489
The problem of realizing an idealized parallel architecture on a (possibly fault-laden) physical architecture is studied. Our formulation performs the mapping in the light of the algorithm that one wants to implement on the idealized...

Optimal simulations between mesh-connected arrays of processors
S. Rao Kosaraju, Mikhail J. Atallah
Pages: 635-650
DOI: 10.1145/44483.44494
Let G and H be two mesh-connected arrays of processors, where G = g1, X g2 X … X...

The parallel complexity of exponentiating polynomials over finite fields
Faith E. Fich, Martin Tompa
Pages: 651-667
DOI: 10.1145/44483.44496
Modular integer exponentiation (given a, e, and m, compute ae mod m) is a fundamental problem in algebraic complexity for which no efficient parallel...

Busy periods for subnetworks in stochastic networks: mean value analysis
Hans Daduna
Pages: 668-674
DOI: 10.1145/44483.44495
The busy period of order n for a subnetwork, which for large n describes heavy traffic periods of that subnetwork, is described for queuing networks. The mean duration of such busy periods and efficient...

The reduction of perturbed Markov generators: an algorithm exposing the role of transient states
Jan Robin Rohlicek, Alan S. Willsky
Pages: 675-696
DOI: 10.1145/44483.44497
A new algorithm for the hierarchical aggregation of singularly perturbed finite-state Markov processes is derived. The approach taken bridges the gap between conceptually simple results for a relatively restricted class of processes and the...

On the power of one-way communication
Jik H. Chang, Oscar H. Ibarra, Anastasios Vergis
Pages: 697-726
DOI: 10.1145/44483.44493
In this paper, a very simple model of parallel computation is considered, and the question of how restricting the flow of data to be one way compares with two-way flow is studied. It is shown that the one-way version is surprisingly very...

Nonconstructive tools for proving polynomial-time decidability
Michael R. Fellows, Michael A. Langston
Pages: 727-739
DOI: 10.1145/44483.44491
Recent advances in graph theory and graph algorithms dramatically alter the traditional view of concrete complexity theory, in which a decision problem is generally shown to be in P by producing an efficient algorithm to solve an optimization...

Fast algorithms for N-dimensional restrictions of hard problems
Friedhelm Meyer auf der Heide
Pages: 740-747
DOI: 10.1145/44483.44490
Let M be a parallel RAM with p processors and arithmetic operations addition and subtraction recognizing L ⊂ Nn in T steps. (Inputs for...

A nonlinear lower bound for random-access machines under logarithmic cost
Arnold Schönhage
Pages: 748-754
DOI: 10.1145/44483.44492
For on-line random-access machines under logarithmic cost, the simple task of storing arbitrary binary inputs has nonlinear complexity. Even if all kinds of powerful internal operations are admitted and reading of storage locations is free of...