Journal of the ACM -- 1996

Volume 43, Number 1, January 1996

Yehuda Afek, Baruch Awerbuch, Serge Plotkin, and Michael Saks. Local management of a global resource in a communication network. Journal of the ACM, 43(1):1-19, January 1996. Abstract, References, etc. [BibTeX entry]
Weidong Chen and David S. Warren. Tabled evaluation with delaying for general logic programs. Journal of the ACM, 43(1):20-74, January 1996. Abstract, References, etc. [BibTeX entry]
Yuh-Jzer Joung and Scott A. Smolka. A comprehensive study of the complexity of multiparty interaction. Journal of the ACM, 43(1):75-115, January 1996. Abstract, References, etc. [BibTeX entry]
Rajeev Alur, Tomás Feder, and Thomas A. Henzinger. The benefits of relaxing punctuality. Journal of the ACM, 43(1):116-146, January 1996. Abstract, References, etc. [BibTeX entry]
Peter Bro Miltersen, Mike Paterson, and Jun Tarui. The asymptotic complexity of merging networks. Journal of the ACM, 43(1):147-165, January 1996. Abstract, References, Citations, etc. [BibTeX entry]
Robert S. Boyer and Yuan Yu. Automated proofs of object code for a widely used microprocessor. Journal of the ACM, 43(1):166-192, January 1996. Abstract, References, Citations, etc. [BibTeX entry]

Bart Selman and Henry Kautz. Knowledge compilation and theory approximation. Journal of the ACM, 43(2):193-224, March 1996. Abstract, References, Citations, etc. [BibTeX entry]
Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225-267, March 1996. Abstract, References, Citations, etc. [BibTeX entry]
Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268-292, March 1996. Abstract, References, Citations, etc. [BibTeX entry]
Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, F. Thomson Leighton, Bojana Obreni\'c, Arnold L. Rosenberg, and Eric J. Schwabe. Optimal emulations by butterfly-like networks. Journal of the ACM, 43(2):293-330, March 1996. Abstract, References, Citations, etc. [BibTeX entry]
Michael T. Goodrich and S. Rao Kosaraju. Sorting on a parallel pointer machine with applications to set expression evaluation. Journal of the ACM, 43(2):331-361, March 1996. Abstract, References, etc. [BibTeX entry]
Pierre-Louis Curien, Thérèse Hardin, and Jean-Jacques Lévy. Confluence properties of weak and strong calculi of explicit substitutions. Journal of the ACM, 43(2):362-397, March 1996. Abstract, References, Citations, etc. [BibTeX entry]

Eugene Santos, Jr.. On linear potential functions for approximating Bayesian computations. Journal of the ACM, 43(3):399-430, May 1996. Abstract, References, etc. [BibTeX entry]
Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. Journal of the ACM, 43(3):431-473, May 1996. Abstract, References, Citations, etc. [BibTeX entry]
Sherry Marcus and V. S. Subrahmanian. Foundations of multimedia database systems. Journal of the ACM, 43(3):474-523, May 1996. Abstract, References, etc. [BibTeX entry]
Mark-Jan Nederhof and Eberhard Bertsch. Linear-time suffix parsing for deterministic languages. Journal of the ACM, 43(3):524-554, May 1996. Abstract, References, etc. [BibTeX entry]
Rob J. van Glabbeek and W. Peter Weijland. Branching time and abstraction in bisimulation semantics. Journal of the ACM, 43(3):555-600, May 1996. Abstract, References, Citations, etc. [BibTeX entry]

David R. Karger and Clifford Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601-640, July 1996. Abstract, References, Citations, etc. [BibTeX entry]
William C. Cheng and Richard R. Muntz. Bounding errors introduced by clustering of customers in closed product-form queueing networks. Journal of the ACM, 43(4):641-669, July 1996. Abstract, References, etc. [BibTeX entry]
Antoni Ko\'scielski and Leszek Pacholski. Complexity of Makanin's algorithm. Journal of the ACM, 43(4):670-684, July 1996. Abstract, References, Citations, etc. [BibTeX entry]
Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving Consensus. Journal of the ACM, 43(4):685-722, July 1996. Abstract, References, Citations, etc. [BibTeX entry]
Ming Li, John Tromp, and Paul M. B. Vitányi. How to share concurrent wait-free variables. Journal of the ACM, 43(4):723-746, July 1996. Abstract, References, Citations, etc. [BibTeX entry]
Nader H. Bshouty and Christino Tamon. On the Fourier spectrum of monotone functions. Journal of the ACM, 43(4):747-770, July 1996. Abstract, References, etc. [BibTeX entry]

Jeffrey Scott Vitter and P. Krishnan. Optimal prefetching via data compression. Journal of the ACM, 43(5):771-793, September 1996. Abstract, References, etc. [BibTeX entry]
Costas Busch and Marios Mavronicolas. A combinatorial treatment of balancing networks. Journal of the ACM, 43(5):794-839, September 1996. Abstract, References, Citations, etc. [BibTeX entry]
Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, and Dawn Wilkins. How many queries are needed to learn? Journal of the ACM, 43(5):840-862, September 1996. Abstract, References, Citations, etc. [BibTeX entry]
Roland Bol and Jan Friso Groote. The meaning of negative premises in transition system specifications. Journal of the ACM, 43(5):863-914, September 1996. Abstract, References, Citations, etc. [BibTeX entry]

Ricardo A. Baeza-Yates and Gaston H. Gonnet. Fast text searching for regular expressions or automaton searching on tries. Journal of the ACM, 43(6):915-936, November 1996. Abstract, References, etc. [BibTeX entry]
Christian W. Omlin and C. Lee Giles. Constructing deterministic finite-state automata in recurrent neural networks. Journal of the ACM, 43(6):937-972, November 1996. Abstract, References, etc. [BibTeX entry]
Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, and Madhu Sudan. Efficient routing in optical networks. Journal of the ACM, 43(6):973-1001, November 1996. Abstract, References, Citations, etc. [BibTeX entry]
Saugata Basu, Richard Pollack, and Marie-Françoise Roy. On the combinatorial and algebraic complexity of quantifier elimination. Journal of the ACM, 43(6):1002-1045, November 1996. Abstract, References, Citations, etc. [BibTeX entry]
Seppo Sippu and Eljas Soisalon-Soininen. An analysis of magic sets and related optimization strategies for logic queries. Journal of the ACM, 43(6):1046-1088, November 1996. Abstract, References, etc. [BibTeX entry]