Journal of the ACM, Volume 42, 1995

Volume 42, Number 1, January 1995

• Thomas Eiter, Georg Gottlob:
  The Complexity of Logic-Based Abduction. 3-42
  
• Bernhard Nebel, Hans-Jürgen Bürckert:
  Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra. 43-66
  
• Paul B. Callahan, S. Rao Kosaraju:
  A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields. 67-90
  
• Andrew A. Chien, Jae H. Kim:
  Planar-Adaptive Routing: Low-Cost Adaptive Networks for Multiprocessors. 91-123
  
• Hagit Attiya, Amotz Bar-Noy, Danny Dolev:
  Sharing Memory Robustly in Message-Passing Systems. 124-142
  
• Danny Dolev, Joseph Y. Halpern, Barbara Simons, H. Raymond Strong:
  Dynamic Fault-Tolerant Clock Synchronization. 143-185
  
• Sibsankar Haldar, K. Vidyasankar:
  Constructing 1-Writer Multireader Multivalued Atomic Variable from Regular Variables. 186-203
  
• C. S. Chang, R. Nelson:
  Bounds on the Speedup and Efficiency of Partial Synchronization in Parallel Processing Systems. 204-231
  
• Bard Bloom, Sorin Istrail, Albert R. Meyer:
  Bisimulation Can't be Traced. 232-268
  
• Manuel Blum, Sampath Kannan:
  Designing Programs that Check Their Work. 269-291
  

Volume 42, Number 2, March 1995

• Fangzhen Lin, Yoav Shoham:
  Provably Correct Theories of Action. 293-320
  
• David R. Karger, Philip N. Klein, Robert Endre Tarjan:
  A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. 321-328
  
• Ke Wang, Weining Zhang, Siu-Cheung Chau:
  Decomposition of Magic Rewriting. 329-381
  
• John N. Tsitsiklis, George D. Stamoulis:
  On the Average Communication Complexity of Asynchronous Distributed Algorithms. 382-400
  
• Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer:
  The Isomorphism Conjecture Fails Relative to a Random Oracle. 401-420
  
• Georg Gottlob:
  NP Trees and Carnap's Modal Logic. 421-457
  
• Rocco De Nicola, Frits W. Vaandrager:
  Three Logics for Branching Bisimulation. 458-487
  
• Kenneth L. Clarkson:
  Las Vegas Algorithms for Linear and Integer Programming when the Dimension is Small. 488-499
  
• Bonnie Berger, Martin L. Brady, Donna J. Brown, Frank Thomson Leighton:
  Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing. 500-542
  

Volume 42, Number 3, May 1995

• Peter van Beek, Rina Dechter:
  On the Minimality and Decomposability of Row-Convex Constraint Networks. 543-561
  
• Kevin J. Compton, Chinya V. Ravishankar:
  Expected Deadlock Time in a Multiprocessing System. 562-583
  
• Yannis A. Korilis, Aurel A. Lazar:
  On the Existence of Equilibria in Noncooperative Optimal Flow Control. 584-613
  
• Paul Bay, Gianfranco Bilardi:
  Deterministic On-Line Routing on Area-Universal Networks. 614-640
  
• Alexander Birman, H. Richard Gail, Sidney L. Hantler, Zvi Rosberg, Moshe Sidi:
  An Optimal Service Policy for Buffer Systems. 641-657
  
• Peter W. O'Hearn, Robert D. Tennent:
  Parametricity and Local Variables. 658-709
  

Volume 42, Number 4, July 1995

• Georg Gottlob:
  Translating Default Logic into Standard Autoepistemic Logic. 711-740
  
• Michael Kifer, Georg Lausen, James Wu:
  Logical Foundations of Object-Oriented and Frame-Based Languages. 741-843
  
• Noga Alon, Raphael Yuster, Uri Zwick:
  Color-Coding. 844-856
  
• Costas Courcoubetis, Mihalis Yannakakis:
  The Complexity of Probabilistic Verification. 857-907
  
• Zvi Galil:
  A Constant-Time Optimal Parallel String-Matching Algorithm. 908-918
  
• Mark H. Nodine, Jeffrey Scott Vitter:
  Greed Sort: Optimal Deterministic Sorting on Parallel Disks. 919-933
  

Volume 42, Number 5, September 1995

• Gagan L. Choudhury, Kin K. Leung, Ward Whitt:
  Calculating Normalization Constants of Closed Queueing Networks by Numerically Inverting Their Generating Functions. 935-970
  
• Elias Koutsoupias, Christos H. Papadimitriou:
  On the k-Server Conjecture. 971-983
  
• Rakesh M. Verma:
  A Theory of Using History for Equational Systems with Applications. 984-1020
  
• Baruch Awerbuch, David Peleg:
  Online Tracking of Mobile Users. 1021-1058
  
• Ewan D. Tempero, Richard E. Ladner:
  Recoverable Sequence Transmission Protocols. 1059-1090
  
• Nabil Kahale:
  Eigenvalues and Expansion of Regular Graphs. 1091-1106
  
• Michele Conforti, Gérard Cornuéjols:
  A Class of Logic Problems Solvable by Linear Programming. 1107-1113
  

Volume 42, Number 6, November 1995

• Michel X. Goemans, David P. Williamson:
  Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. 1115-1145
  
• Rusins Freivalds, Efim B. Kinber, Carl H. Smith:
  On the Impact of Forgetting on Learning Machines. 1146-1168
  
• Joan Boyar, Gilles Brassard, René Peralta:
  Subquadratic Zero-Knowledge. 1169-1193
  
• Jan A. Bergstra, J. V. Tucker:
  Equational Specifications, Complete Term Rewriting Systems, and Computable and Semicomputable Algebras. 1194-1230
  
• Yehuda Afek, David S. Greenberg, Michael Merritt, Gadi Taubenfeld:
  Computing With Faulty Shared Objects. 1231-1274
  
• Yoshihito Toyama, Jan Willem Klop, Hendrik Pieter Barendregt:
  Termination for Direct Sums of Left-Linear Complete Term Rewriting Systems. 1275-1304