Journal of the ACM, Volume 43, 1996

Volume 43, Number 1, January 1996

• Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael E. Saks:
  Local Management of a Global Resource in a Communication Network. 1-19
  
• Weidong Chen, David Scott Warren:
  Tabled Evaluation With Delaying for General Logic Programs. 20-74
  
• Yuh-Jzer Joung, Scott A. Smolka:
  A Comprehensive Study of the Complexity of Multiparty Interaction. 75-115
  
• Rajeev Alur, Tomás Feder, Thomas A. Henzinger:
  The Benefits of Relaxing Punctuality. 116-146
  
• Peter Bro Miltersen, Mike Paterson, Jun Tarui:
  The Asymptotic Complexity of Merging Networks. 147-165
  
• Robert S. Boyer, Yuan Yu:
  Automated Proofs of Object Code for a Widely Used Microprocessor. 166-192
  

Volume 43, Number 2, March 1996

• Bart Selman, Henry A. Kautz:
  Knowledge Compilation and Theory Approximation. 193-224
  
• Tushar Deepak Chandra, Sam Toueg:
  Unreliable Failure Detectors for Reliable Distributed Systems. 225-267
  
• Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy:
  Interactive Proofs and the Hardness of Approximating Cliques. 268-292
  
• Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, Frank Thomson Leighton, Bojana Obrenic, Arnold L. Rosenberg, Eric J. Schwabe:
  Optimal Emulations by Butterfly-Like Networks. 293-330
  
• Michael T. Goodrich, S. Rao Kosaraju:
  Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation. 331-361
  
• Pierre-Louis Curien, Thérèse Hardin, Jean-Jacques Lévy:
  Confluence Properties of Weak and Strong Calculi of Explicit Substitutions. 362-397
  

Volume 43, Number 3, May 1996

• Eugene Santos Jr.:
  On Linear Potential Functions for Approximating Bayesian Computations. 399-430
  
• Oded Goldreich, Rafail Ostrovsky:
  Software Protection and Simulation on Oblivious RAMs. 431-473
  
• Sherry Marcus, V. S. Subrahmanian:
  Foundations of Multimedia Database Systems. 474-523
  
• Mark-Jan Nederhof, Eberhard Bertsch:
  Linear-Time Suffix Parsing for Deterministic Languages. 524-554
  
• Rob J. van Glabbeek, W. P. Weijland:
  Branching Time and Abstraction in Bisimulation Semantics. 555-600
  

Volume 43, Number 4, July 1996

• David R. Karger, Clifford Stein:
  A New Approach to the Minimum Cut Problem. 601-640
  
• William C. Cheng, Richard R. Muntz:
  Bounding Errors Introduced by Clustering of Customers in Closed Product-Form Queueing Networks. 641-669
  
• Antoni Koscielski, Leszek Pacholski:
  Complexity of Makanin's Algorithm. 670-684
  
• Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg:
  The Weakest Failure Detector for Solving Consensus. 685-722
  
• Ming Li, John Tromp, Paul M. B. Vitányi:
  How to Share Concurrent Wait-Free Variables. 723-746
  
• Nader H. Bshouty, Christino Tamon:
  On the Fourier Spectrum of Monotone Functions. 747-770
  

Volume 43, Number 5, September 1996

• Jeffrey Scott Vitter, P. Krishnan:
  Optimal Prefetching via Data Compression. 771-793
  
• Costas Busch, Marios Mavronicolas:
  A Combinatorial Treatment of Balancing Networks. 794-839
  
• Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay V. Raghavan, Dawn Wilkins:
  How Many Queries Are Needed to Learn? 840-862
  
• Roland N. Bol, Jan Friso Groote:
  The Meaning of Negative Premises in Transition System Specifications. 863-914
  

Volume 43, Number 6, November 1996

• Ricardo A. Baeza-Yates, Gaston H. Gonnet:
  Fast Text Searching for Regular Expressions or Automaton Searching on Tries. 915-936
  
• Christian W. Omlin, C. Lee Giles:
  Constructing Deterministic Finite-State Automata in Recurrent Neural Networks. 937-972
  
• Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan:
  Efficient Routing in Optical Networks. 973-1001
  
• Saugata Basu, Richard Pollack, Marie-Françoise Roy:
  On the Combinatorial and Algebraic Complexity of Quantifier Elimination. 1002-1045
  
• Seppo Sippu, Eljas Soisalon-Soininen:
  An Analysis of Magic Sets and Related Optimization Strategies for Logic Queries. 1046-1088