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