Journal of the ACM -- 1995

Volume 42, Number 1, January 1995

• Thomas Eiter and Georg Gottlob. The complexity of logic-based abduction. Journal of the ACM, 42(1):3-42, January 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Bernhard Nebel and Hans-Jürgen Bürckert. Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra. Journal of the ACM, 42(1):43-66, January 1995. Abstract, References, etc. [BibTeX entry]

• Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM, 42(1):67-90, January 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Andrew A. Chien and Jae H. Kim. Planar-adaptive routing: Low-cost adaptive networks for multiprocessors. Journal of the ACM, 42(1):91-123, January 1995. Abstract, etc. [BibTeX entry]

• Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. Journal of the ACM, 42(1):124-142, January 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Danny Dolev, Joseph Y. Halpern, Barbara Simons, and Ray Strong. Dynamic fault-tolerant clock synchronization. Journal of the ACM, 42(1):143-185, January 1995. Abstract, References, etc. [BibTeX entry]

• S. Haldar and K. Vidyasankar. Constructing 1-writer multireader multivalued atomic variable from regular variables. Journal of the ACM, 42(1):186-203, January 1995. Abstract, References, Citations, etc. [BibTeX entry]

• C. S. Chang and R. Nelson. Bounds on the speedup and efficiency of partial synchronization in parallel processing systems. Journal of the ACM, 42(1):204-231, January 1995. Abstract, References, etc. [BibTeX entry]

• Bard Bloom, Sorin Istrail, and Albert R. Meyer. Bisimulation can't be traced. Journal of the ACM, 42(1):232-268, January 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Manuel Blum and Sampath Kannan. Designing programs that check their work. Journal of the ACM, 42(1):269-291, January 1995. Abstract, References, Citations, etc. [BibTeX entry]

Volume 42, Number 2, March 1995

• Fangzhen Lin and Yoav Shoham. Provably correct theories of action. Journal of the ACM, 42(2):293-320, March 1995. Abstract, References, etc. [BibTeX entry]

• David R. Karger, Philip N. Klein, and Robert E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2):321-328, March 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Ke Wang, Weining Zhang, and Siu-Cheung Chau. Decomposition of magic rewriting. Journal of the ACM, 42(2):329-381, March 1995. Abstract, etc. [BibTeX entry]

• John N. Tsitsiklis and George D. Stamoulis. On the average communication complexity of asynchronous distributed algorithms. Journal of the ACM, 42(2):382-400, March 1995. Abstract, References, etc. [BibTeX entry]

• Stuart A. Kurtz, Stephen R. Mahaney, and James S. Royer. The isomorphism conjecture fails relative to a random oracle. Journal of the ACM, 42(2):401-420, March 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Georg Gottlob. NP trees and Carnap's modal logic. Journal of the ACM, 42(2):421-457, March 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Rocco De Nicola and Frits Vaandrager. Three logics for branching bisimulation. Journal of the ACM, 42(2):458-487, March 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Kenneth L. Clarkson. Las Vegas algorithms for linear and integer programming when the dimension is small. Journal of the ACM, 42(2):488-499, March 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Bonnie Berger, Martin Brady, Donna Brown, and Tom Leighton. Nearly optimal algorithms and bounds for multilayer channel routing. Journal of the ACM, 42(2):500-542, March 1995. Abstract, References, Citations, etc. [BibTeX entry]

Volume 42, Number 3, May 1995

• Peter van Beek and Rina Dechter. On the minimality and global consistency of row-convex constraint networks. Journal of the ACM, 42(3):543-561, May 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Kevin J. Compton and Chinya Ravishankar. Expected deadlock time in a multiprocessing system. Journal of the ACM, 42(3):562-583, May 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Yannis A. Korilis and Aurel A. Lazar. On the existence of equilibria in noncooperative optimal flow control. Journal of the ACM, 42(3):584-613, May 1995. Abstract, etc. [BibTeX entry]

• Paul Bay and Gianfranco Bilardi. Deterministic on-line routing on area-universal networks. Journal of the ACM, 42(3):614-640, May 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Alexander Birman, H. Richard Gail, Sidney L. Hantler, Zvi Rosberg, and Moshe Sidi. An optimal service policy for buffer systems. Journal of the ACM, 42(3):641-657, May 1995. Abstract, References, etc. [BibTeX entry]

• P. W. O'Hearn and R. D. Tennent. Parametricity and local variables. Journal of the ACM, 42(3):658-709, May 1995. Abstract, References, Citations, etc. [BibTeX entry]

Volume 42, Number 4, July 1995

• Georg Gottlob. Translating default logic into standard autoepistemic logic. Journal of the ACM, 42(4):711-740, July 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Michael Kifer, Georg Lausen, and James Wu. Logical foundations of object-oriented and frame-based languages. Journal of the ACM, 42(4):741-843, July 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, July 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Costas Courcoubetis and Mihalis Yannakakis. The complexity of probabilistic verification. Journal of the ACM, 42(4):857-907, July 1995. Abstract, References, etc. [BibTeX entry]

• Zvi Galil. A constant-time optimal parallel string-matching algorithm. Journal of the ACM, 42(4):908-918, July 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Mark H. Nodine and Jeffrey Scott Vitter. Greed sort: Optimal deterministic sorting on parallel disks. Journal of the ACM, 42(4):919-933, July 1995. Abstract, References, Citations, etc. [BibTeX entry]

Volume 42, Number 5, September 1995

• Gagan L. Choudhury, Kin K. Leung, and Ward Whitt. Calculating normalization constants of closed queueing networks by numerically inverting their generating functions. Journal of the ACM, 42(5):935-970, September 1995. Abstract, References, etc. [BibTeX entry]

• Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. Journal of the ACM, 42(5):971-983, September 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Rakesh M. Verma. A theory of using history for equational systems with applications. Journal of the ACM, 42(5):984-1020, September 1995. Abstract, References, etc. [BibTeX entry]

• Baruch Awerbuch and David Peleg. Online tracking of mobile users. Journal of the ACM, 42(5):1021-1058, September 1995. Abstract, References, etc. [BibTeX entry]

• Ewan D. Tempero and Richard E. Ladner. Recoverable sequence transmission protocols. Journal of the ACM, 42(5):1059-1090, September 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Nabil Kahale. Eigenvalues and expansion of regular graphs. Journal of the ACM, 42(5):1091-1106, September 1995. Abstract, References, Citations, etc. [BibTeX entry]

• Michel Conforti and Gérard Cornuéjols. A class of logic problems solvable by linear programming. Journal of the ACM, 42(5):1107-1113, September 1995. Abstract, References, etc. [BibTeX entry]

Volume 42, Number 6, November 1995

• Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115-1145, November 1995. References, Citations, etc. [BibTeX entry]

• R\=usi\c{n}\v{s} Freivalds, Efim Kinber, and Carl H. Smith. On the impact of forgetting on learning machines. Journal of the ACM, 42(6):1146-1168, November 1995. References, Citations, etc. [BibTeX entry]

• Joan Boyar, Gilles Brassard, and René Peralta. Subquadratic zero-knowledge. Journal of the ACM, 42(6):1169-1193, November 1995. References, Citations, etc. [BibTeX entry]

• J. A. Bergstra and J. V. Tucker. Equational specifications, complete term rewriting systems, and computable and semicomputable algebras. Journal of the ACM, 42(6):1194-1230, November 1995. References, Citations, etc. [BibTeX entry]

• Yehuda Afek, David S. Greenberg, Michael Merritt, and Gadi Taubenfeld. Computing with faulty shared ojects. Journal of the ACM, 42(6):1231-1274, November 1995. References, Citations, etc. [BibTeX entry]

• Y. Toyama, Jan Willem Klop, and H. P. Barendregt. Termination for direct sums of left-linear complete term rewriting systems. Journal of the ACM, 42(6):1275-1304, November 1995. References, Citations, etc. [BibTeX entry]

Shortcuts: