Journal of the ACM -- 1994

Volume 41, Number 1, January 1994

• Michael J. Fischer and Michael S. Paterson. Fishspear: A priority queue algorithm. Journal of the ACM, 41(1):3-30, January 1994. References. [BibTeX entry]

• Daniel N. Rockmore. Efficient computation of Fourier inversion for finite groups. Journal of the ACM, 41(1):31-66, January 1994. References. [BibTeX entry]

• Michael Kearns and Leslie Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. Journal of the ACM, 41(1):67-95, January 1994. References and Citations. [BibTeX entry]

• Pekka Orponen, Ker-I Ko, Uwe Schöning, and Osamu Watanabe. Instance complexity. Journal of the ACM, 41(1):96-121, January 1994. References and Citations. [BibTeX entry]

• Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds on the time to reach agreement in the presence of timing uncertainty. Journal of the ACM, 41(1):122-152, January 1994. References and Citations. [BibTeX entry]

• Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153-180, January 1994. References and Citations. [BibTeX entry]

• Rajeev Alur and Thomas A. Henzinger. A really temporal logic. Journal of the ACM, 41(1):181-204, January 1994. References and Citations. [BibTeX entry]

Volume 41, Number 2, March 1994

• Moshe Dubiner, Zvi Galil, and Edith Magen. Faster tree pattern matching. Journal of the ACM, 41(2):205-213, March 1994. References and Citations. [BibTeX entry]

• Samir Khuller and Uzi Vishkin. Biconnectivity approximations and graph carvings. Journal of the ACM, 41(2):214-235, March 1994. References and Citations. [BibTeX entry]

• Leo Bachmair and Nachum Dershowitz. Equational inference, canonical proofs, and proof orderings. Journal of the ACM, 41(2):236-276, March 1994. References. [BibTeX entry]

• Karl Abrahamson, Andrew Adler, Lisa Higham, and David Kirkpatrick. Tight lower bounds for probabilistic solitude verification on anonymous rings. Journal of the ACM, 41(2):277-310, March 1994. References and Citations. [BibTeX entry]

• Ambuj K. Singh, James H. Anderson, and Mohamed G. Gouda. The elusive atomic register. Journal of the ACM, 41(2):311-339, March 1994. References and Citations. [BibTeX entry]

• Ronald Fagin and Joseph Y. Halpern. Reasoning about knowledge and probability. Journal of the ACM, 41(2):340-367, March 1994. References and Citations. [BibTeX entry]

• A. J. Kfoury, J. Tiuryn, and P. Urzyczyn. An analysis of ML typability. Journal of the ACM, 41(2):368-398, March 1994. References and Citations. [BibTeX entry]

• Michael Cosnard and El Mostafa Daoudi. Optimal algorithms for parallel givens factorization on a coarse-grained PRAM. Journal of the ACM, 41(2):399-421, March 1994. References. [BibTeX entry]

• Noga Alon and Nimrod Megiddo. Parallel linear programming in fixed dimension almost surely in constant time. Journal of the ACM, 41(2):422-434, March 1994. References and Citations. [BibTeX entry]

Volume 41, Number 3, May 1994

• Peter B. Ladkin and Roger D. Maddux. On binary constraint problems. Journal of the ACM, 41(3):435-469, May 1994. Citations. [BibTeX entry]

• Avrim Blum. New approximation algorithms for graph coloring. Journal of the ACM, 41(3):470-516, May 1994. References and Citations. [BibTeX entry]

• Doron Drusinsky and David Harel. On the power of bounded concurrency I: Finite automata. Journal of the ACM, 41(3):517-539, May 1994. References and Citations. [BibTeX entry]

• Tirza Hirst and David Harel. On the power of bounded concurrency II: Pushdown automata. Journal of the ACM, 41(3):540-554, May 1994. References and Citations. [BibTeX entry]

• Ronald L. Rivest and Robert E. Schapire. Diversity-based inference of finite automata. Journal of the ACM, 41(3):555-589, May 1994. References and Citations. [BibTeX entry]

Volume 41, Number 4, July 1994

• Wray L. Buntine and Hans-Jürgen Bürckert. On solving equations and disequations. Journal of the ACM, 41(4):591-629, July 1994. References. [BibTeX entry]

• Avrim Blum, Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis. Linear approximation of shortest superstrings. Journal of the ACM, 41(4):630-647, July 1994. References and Citations. [BibTeX entry]

• Adrian E. Conway, Eugene Pinsky, and Srinivasan Tridandapani. Efficient decomposition methods for the analysis of multi-facility blocking models. Journal of the ACM, 41(4):648-675, July 1994. [BibTeX entry]

• John C. S. Lui and Richard R. Muntz. Computing bounds on steady state availability of repairable computer systems. Journal of the ACM, 41(4):676-707, July 1994. References. [BibTeX entry]

• Timothy C. Bell and Ian H. Witten. The relationship between greedy parsing and symbolwise text compression. Journal of the ACM, 41(4):708-724, July 1994. References. [BibTeX entry]

• Hagit Attiya, Nancy Lynch, and Nir Shavit. Are wait-free algorithms fast? Journal of the ACM, 41(4):725-763, July 1994. References and Citations. [BibTeX entry]

• John Reif and Micha Sharir. Motion planning in the presence of moving obstacles. Journal of the ACM, 41(4):764-790, July 1994. References. [BibTeX entry]

• Shaodi Gao and Michael Kaufmann. Channel routing of multiterminal nets. Journal of the ACM, 41(4):791-818, July 1994. References and Citations. [BibTeX entry]

Volume 41, Number 5, September 1994

• Peter K. Rathmann, Marianne Winslett, and Mark Manasse. Circumscription with homomorphisms: Solving the equality and counterexample problems. Journal of the ACM, 41(5):819-873, September 1994. [BibTeX entry]

• Christopher J. Glass and Lionel M. Ni. The turn model for adaptive routing. Journal of the ACM, 41(5):874-902, September 1994. Citations. [BibTeX entry]

• Yves Dallery, Zhen Liu, and Don Towsley. Equivalence, reversibility, symmetry and concavity properties in fork-join queuing networks with blocking. Journal of the ACM, 41(5):903-942, September 1994. References. [BibTeX entry]

• James R. Driscoll, Daniel D. K. Sleator, and Robert E. Tarjan. Fully persistent lists with catenation. Journal of the ACM, 41(5):943-959, September 1994. References and Citations. [BibTeX entry]

• Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960-981, September 1994. References, Citations, etc. [BibTeX entry]

• James A. Storer and John H. Reif. Shortest paths in the plane with polygonal obstacles. Journal of the ACM, 41(5):982-1012, September 1994. References. [BibTeX entry]

• John H. Reif and James A. Storer. A single-exponential upper bounds for finding shortest paths in three dimensions. Journal of the ACM, 41(5):1013-1019, September 1994. References and Citations. [BibTeX entry]

• James Aspnes, Maurice Herlihy, and Nir Shavit. Counting networks. Journal of the ACM, 41(5):1020-1048, September 1994. References and Citations. [BibTeX entry]

Volume 41, Number 6, November 1994

• Mikhail J. Atallah, Michael T. Goodrich, and S. Rao Kosaraju. Parallel algorithms for evaluating sequences of set-manipulation operations. Journal of the ACM, 41(6):1049-1088, November 1994. References and Citations. [BibTeX entry]

• Tal Rabin. Robust sharing of secrets when the dealer is honest or cheating. Journal of the ACM, 41(6):1089-1109, November 1994. References and Citations. [BibTeX entry]

• Keith W. Ross, Danny H. K. Tsang, and Jie Wang. Monte Carlo summation and integration applied to multiclass queuing networks. Journal of the ACM, 41(6):1110-1135, November 1994. References. [BibTeX entry]

• Richard M. Karp. Probabilistic recurrence relations. Journal of the ACM, 41(6):1136-1150, November 1994. References and Citations. [BibTeX entry]

• Jeffrey F. Naughton and Raghu Ramakrishnan. How to forget the past without repeating it. Journal of the ACM, 41(6):1151-1177, November 1994. [BibTeX entry]

• Colin Bell, Anil Nerode, Raymond T. Ng, and V. S. Subrahmanian. Mixed integer programming methods for computing nonmonotonic deductive databases. Journal of the ACM, 41(6):1178-1215, November 1994. Citations. [BibTeX entry]

• Kenneth A. Ross. Modular stratification and magic sets for datalog programs with negation. Journal of the ACM, 41(6):1216-1266, November 1994. References and Citations. [BibTeX entry]

• Yehuda Afek, Hagit Attiya, Alan Fekete, Michael Fischer, Nancy Lynch, Yishay Mansour, Dai-Wei Wang, and Lenore Zuck. Reliable communication over unreliable channels. Journal of the ACM, 41(6):1267-1297, November 1994. References and Citations. [BibTeX entry]

• Michael Kearns, Ming Li, and Leslie Valiant. Learning Boolean formulas. Journal of the ACM, 41(6):1298-1328, November 1994. References and Citations. [BibTeX entry]

• Rajeev Motwani. Average-case analysis of algorithms for matchings and related problems. Journal of the ACM, 41(6):1329-1356, November 1994. References. [BibTeX entry]

Shortcuts: