**On solving equations and disequations**

Wray L. Buntine, Hans-Jürgen Bürckert

Pages: 591-629

DOI: 10.1145/179812.179813

We are interested in the problem of solving a system<si=ti:1≤i≤n,pj≠qj:1≤j≤m> of equations and disequations, also known as...

**Linear approximation of shortest superstrings**

Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis

Pages: 630-647

DOI: 10.1145/179812.179818

We consider the following problem: given a collection of strings s1,…, sm, find the shortest string s such that each...

**Efficient decomposition methods for the analysis of multi-facility blocking models**

Adrian E. Conway, Eugene Pinsky, Srinivasan Tridandapani

Pages: 648-675

DOI: 10.1145/179812.179838

Three new decomposition methods are developed for the exact analysis of stochastic multi-facility blocking models of the product-form type. The first is a basic decomposition algorithm that reduces the analysis of blocking probabilities to that...

**Computing bounds on steady state availability of repairable computer systems**

John C. S. Lui, Richard R. Muntz

Pages: 676-707

DOI: 10.1145/179812.179848

One of the most important performance measures for computer system designers is system availability. Most often, Markov models are used in representing systems for dependability/availability analysis. Due to complex interactions between...

**The relationship between greedy parsing and symbolwise text compression**

Timothy C. Bell, Ian H. Witten

Pages: 708-724

DOI: 10.1145/179812.179892

Text compression methods can be divided into two classes: symbolwise and parsing. Symbolwise methods assign codes to individual symbols, while parsing methods assign codes to groups of consecutive symbols...

**Are wait-free algorithms fast?**

Hagit Attiya, Nancy Lynch, Nir Shavit

Pages: 725-763

DOI: 10.1145/179812.179902

The time complexity of wait-free algorithms in “normal” executions, where no failures occur and processes operate at approximately the same speed, is considered. A lower bound of log n on the time complexity of any...

**Motion planning in the presence of moving obstacles**

John Reif, Micha Sharir

Pages: 764-790

DOI: 10.1145/179812.179911

This paper investigates the computational complexity of planning the motion of a body B in 2-D or 3-D space, so as to avoid collision with moving obstacles of known, easily computed, trajectories. Dynamic movement problems are of fundamental...

**Channel routing of multiterminal nets**

Shaodi Gao, Michael Kaufmann

Pages: 791-818

DOI: 10.1145/179812.179927

This paper presents new upper bounds for channel routing of multiterminal nets, which answers the long-standing open question whether or not multiterminal problems really require channels two times wider than 2-terminal problems. We transform...