Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 39 Issue 3, July 1992

A little knowledge goes a long way: knowledge-based derivations and correctness proofs for a family of protocols
Joseph Y. Halpern, Lenore D. Zuck
Pages: 449-478
DOI: 10.1145/146637.146638
A high-level, knowledge-based approach for deriving a family of protocols for the sequence transmission problem is presented. The protocols of Aho et al. [2, 3], the Alternating Bit protocol [5], and Stenning's protocol [44] are...

The pagenumber of genus g graphs is O(g)
Lenwood S. Heath, Sorin Istrail
Pages: 479-501
DOI: 10.1145/146637.146643
In 1979, Bernhart and Kainen conjectured that graphs of fixed genus g ≥ 1 have unbounded pagenumber. In this paper, it is proven that genus g graphs can be embedded in O(g)...

An efficient algorithm for a task allocation problem
A. Billionnet, M. C. Costa, A. Sutter
Pages: 502-518
DOI: 10.1145/146637.146646
This paper presents an efficient algorithm to solve one of the task allocation problems. Task assignment in an heterogeneous multiple processors system is investigated. The cost function is formulated in order to measure the intertask...

Sparse dynamic programming I: linear cost functions
David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano
Pages: 519-545
DOI: 10.1145/146637.146650
Dynamic programming solutions to a number of different recurrence equations for sequence comparison and for RNA secondary structure prediction are considered. These recurrences are defined over a number of points that is quadratic in the input...

Sparse dynamic programming II: convex and concave cost functions
David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano
Pages: 546-567
DOI: 10.1145/146637.146656
Dynamic programming solutions to two recurrence equations, used to compute a sequence alignment from a set of matching fragments between two strings, and to predict RNA secondary structure, are considered. These recurrences are defined over a...

How fair is fair queuing
A. G. Greenberg, N. Madras
Pages: 568-598
DOI: 10.1145/146637.146658

The membership problem in aperiodic transformation monoids
M. Beaudry, P. McKenzie, D. Thérien
Pages: 599-616
DOI: 10.1145/146637.146661
The problem of testing membership in aperiodic or “group-free” transformation monoids is the natural counterpart to the well-studied membership problem in permutation groups. The class A of all finite aperiodic monoids...

On pointers versus addresses
Amir M. Ben-Amram, Zvi Galil
Pages: 617-648
DOI: 10.1145/146637.146666

Learning via queries
William I. Gasarch, Carl H. Smith
Pages: 649-674
DOI: 10.1145/146637.146670
Traditional work in inductive inference has been to model a learner receiving data about a function f and trying to learn the function. The data is usually just the values f(0), f(1),…....

Reasoning about systems with many processes
Steven M. German, A. Prasad Sistla
Pages: 675-735
DOI: 10.1145/146637.146681
Methods are given for automatically verifying temporal properties of concurrent systems containing an arbitrary number of finite-state processes that communicate using CCS actions. TWo models of systems are considered. Systems in the first model...

Monotone circuits for matching require linear depth
Ran Raz, Avi Wigderson
Pages: 736-744
DOI: 10.1145/146637.146684
It is proven that monotone circuits computing the perfect matching function on n-vertex graphs require &OHgr;(n) depth. This implies an exponential gap between the depth of monotone and nonmonotone...