ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 41 Issue 4, July 1994

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