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

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

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

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

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

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

Last update Fri May 25 09:28:40 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page