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