Journal of the ACM, Volume 47, 2000

Volume 47, Number 1, January 2000

• Yair Bartal, Eddie Grove:
  The harmonic k-server algorithm is competitive. 1-15
  
• Patrick W. Dymond, Walter L. Ruzzo:
  Parallel RAMs with owned global memory and deterministic context-free language recognition. 16-45
  
• David R. Karger:
  Minimum cuts in near-linear time. 46-76
  
• Thomas Eiter, Yuri Gurevich, Georg Gottlob:
  Existential second-order logic over strings. 77-131
  
• Edith Cohen:
  Polylog-time and near-linear work approximation scheme for undirected shortest paths. 132-166
  
• Peter W. O'Hearn, John C. Reynolds:
  From Algol to polymorphic linear lambda-calculus. 167-223
  

Volume 47, Number 2, March 2000

• Matthew K. Franklin, Zvi Galil, Moti Yung:
  Eavesdropping games: a graph-theoretic approach to privacy in distributed systems. 225-243
  
• George Varghese, Mahesh Jayaram:
  The fault span of crash failures. 244-293
  
• Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou:
  An O(log(n)^4/3) space algorithm for (s, t) connectivity in undirected graphs. 294-311
  
• Orna Kupferman, Moshe Y. Vardi, Pierre Wolper:
  An automata-theoretic approach to branching-time model checking. 312-360
  
• Roberto Giacobazzi, Francesco Ranzato, Francesca Scozzari:
  Making abstract interpretations complete. 361-416
  

Volume 47, Number 3, May 2000

• John F. Canny, Ioannis Z. Emiris:
  A subdivision-based algorithm for the sparse resultant. 417-451
  
• Ronen I. Brafman, Moshe Tennenholtz:
  An axiomatic treatment of three qualitative decision criteria. 452-482
  
• Juhani Karhumäki, Filippo Mignosi, Wojciech Plandowski:
  The expressibility of languages and relations by word equations. 483-505
  
• Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, Stefano Varricchio:
  Learning functions represented as multiplicity automata. 506-530
  
• Benjamin C. Pierce, Davide Sangiorgi:
  Behavioral equivalence in the polymorphic pi-calculus. 531-584
  

Volume 47, Number 4, July 2000

• Guy Even, Joseph Naor, Satish Rao, Baruch Schieber:
  Divide-and-conquer approximation algorithms via spreading metrics. 585-616
  
• Bala Kalyanasundaram, Kirk Pruhs:
  Speed is as powerful as clairvoyance. 617-643
  
• Michael Benedikt, Leonid Libkin:
  Relational queries over interpreted structures. 644-680
  
• Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender:
  Complexity of finite-horizon Markov decision process problems. 681-720
  
• J. P. Rawling, S. A. Selesnick:
  Orthologic and quantum logic: models and computational elements. 721-751
  
• Eitan Altman, Bruno Gaujal, Arie Hordijk:
  Balanced sequences and optimal routing. 752-775
  
• Sergio Antoy, Rachid Echahed, Michael Hanus:
  A needed narrowing strategy. 776-822
  

Volume 47, Number 5, September 2000

• Joseph Y. Halpern:
  Editorial: a bill of rights and responsibilities. 823-825
  
• David A. Cohen, Peter Jeavons, Peter Jonsson, Manolis Koubarakis:
  Building tractable disjunctive constraints. 826-853
  
• Leslie G. Valiant:
  A neuroidal architecture for cognitive computation. 854-882
  
• Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, Shang-Hua Teng:
  Sliver exudation. 883-904
  
• Tao Jiang, Ming Li, Paul M. B. Vitányi:
  A lower bound on the average-case complexity of shellsort. 905-911
  
• Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, Mark R. Tuttle:
  Tight bounds for k-set agreement. 912-943
  
• Miroslaw Kutylowski, Krzysztof Lorys, Brigitte Oesterdiekhoff, Rolf Wanka:
  Periodification scheme: constructing sorting networks with constant period. 944-967
  

Volume 47, Number 6, November 2000

• Susanne Albers, Naveen Garg, Stefano Leonardi:
  Minimizing stall time in single and parallel disk systems. 969-986
  
• Martin Farach-Colton, Paolo Ferragina, S. Muthukrishnan:
  On the sorting-complexity of suffix tree construction. 987-1011
  
• Bernard Chazelle:
  The soft heap: an approximate priority queue with optimal error rate. 1012-1027
  
• Bernard Chazelle:
  A minimum spanning tree algorithm with Inverse-Ackermann type complexity. 1028-1047
  
• Leslie Ann Goldberg, Philip D. MacKenzie, Mike Paterson, Aravind Srinivasan:
  Contention resolution with constant expected delay. 1048-1096