Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 43 Issue 2, March 1996

Knowledge compilation and theory approximation
Bart Selman, Henry Kautz
Pages: 193-224
DOI: 10.1145/226643.226644
Computational efficiency is a central concern in the design of knowledge representation systems. In order to obtain efficient systems, it has been suggested that one should limit the form of the statements in the knowledge base or use an...

Unreliable failure detectors for reliable distributed systems
Tushar Deepak Chandra, Sam Toueg
Pages: 225-267
DOI: 10.1145/226643.226647
We introduce the concept of unreliable failure detectors and study how they can be used to solve Consensus in asynchronous systems with crash failures. We characterise unreliable failure detectors in terms of two properties—completeness...

Interactive proofs and the hardness of approximating cliques
Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, Mario Szegedy
Pages: 268-292
DOI: 10.1145/226643.226652
The contribution of this paper is two-fold. First, a connection is established between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient multi-prover interactive proof for NP...

Optimal emulations by butterfly-like networks
Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, F. Thomson Leighton, Bojana Obrenic, Arnold L. Rosenberg, Eric J. Schwabe
Pages: 293-330
DOI: 10.1145/226643.226658

Sorting on a parallel pointer machine with applications to set expression evaluation
Michael T. Goodrich, S. Rao Kosaraju
Pages: 331-361
DOI: 10.1145/226643.226670
We present optimal algorithms for sorting on parallel CREW and EREW versions of the pointer machine model. Intuitively, one can view our methods as being based on a parallel mergesort using linked lists rather than arrays (the usual parallel...

Confluence properties of weak and strong calculi of explicit substitutions
Pierre-Louis Curien, Thérèse Hardin, Jean-Jacques Lévy
Pages: 362-397
DOI: 10.1145/226643.226675
Categorical combinators [Curien 1986/1993; Hardin 1989; Yokouchi 1989] and more recently &lgr;&sgr;-calculus [Abadi 1991; Hardin and Le´vy 1989], have been introduced to provide an explicit treatment of substitutions in the &lgr;-calculus....