Journal of the ACM -- 1981

Volume 28, Number 1, January 1981

• Shimon Even and Yossi Shiloach. An on-line edge-deletion problem. Journal of the ACM, 28(1):1-4, January 1981. Citations. [BibTeX entry]

• Yehoshua Perl and Stephen R. Schach. Max-min tree partitioning. Journal of the ACM, 28(1):5-15, January 1981. [BibTeX entry]

• Michael Rodeh, Vaughan R. Pratt, and Shimon Even. Linear algorithm for data compression via string matching. Journal of the ACM, 28(1):16-24, January 1981. Citations. [BibTeX entry]

• Philip A. Bernstein and Dah-Ming W. Chiu. Using semi-joins to solve relational queries. Journal of the ACM, 28(1):25-40, January 1981. Citations. [BibTeX entry]

• Witold Lipski, Jr.. On databases with incomplete information. Journal of the ACM, 28(1):41-70, January 1981. Citations. [BibTeX entry]

• G. W. Wasilkowski. n-evaluation conjecture for multipoint iterations for the solution of scalar nonlinear equations. Journal of the ACM, 28(1):71-80, January 1981. Citations. [BibTeX entry]

• James O. Achugbue and Francis Y. Chin. Bounds on schedules for independent tasks with similar execution times. Journal of the ACM, 28(1):81-99, January 1981. [BibTeX entry]

• J. Bruno, P. Downey, and G. N. Frederickson. Sequencing tasks with exponential service times to minimize the expected flow time or makespan. Journal of the ACM, 28(1):100-113, January 1981. [BibTeX entry]

• Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. Journal of the ACM, 28(1):114-133, January 1981. Citations. [BibTeX entry]

• Zvi Galil. String matching in real time. Journal of the ACM, 28(1):134-149, January 1981. Citations. [BibTeX entry]

• David G. Kirkpatrick. A unified lower bound for selection and set partitioning problems. Journal of the ACM, 28(1):150-165, January 1981. Citations. [BibTeX entry]

• Benton L. Leong and Joel I. Seiferas. New real-time simulations of multihead tape units. Journal of the ACM, 28(1):166-180, January 1981. Citations. [BibTeX entry]

• John H. Rowland and Philip J. Davis. On the use of transcendentals for program testing. Journal of the ACM, 28(1):181-190, January 1981. [BibTeX entry]

Volume 28, Number 2, April 1981

• Peter B. Andrews. Theorem proving via general mappings. Journal of the ACM, 28(2):193-214, April 1981. Citations. [BibTeX entry]

• Prabhaker Mateti. A decision procedure for the correctness of a class of programs. Journal of the ACM, 28(2):215-232, April 1981. [BibTeX entry]

• Gerald E. Peterson and Mark E. Stickel. Complete sets of reductions for some equational theories. Journal of the ACM, 28(2):233-264, April 1981. Citations. [BibTeX entry]

• C. K. Chu. A note on multiple error detection in ASCII numeric data communication. Journal of the ACM, 28(2):265-269, April 1981. Citations. [BibTeX entry]

• Kishor S. Trivedi and Timothy M. Sigmon. Optimal design of linear storage hierarchies. Journal of the ACM, 28(2):270-288, April 1981. [BibTeX entry]

• Gaston H. Gonnet. Expected length of the longest probe sequence in hash code searching. Journal of the ACM, 28(2):289-304, April 1981. Citations. [BibTeX entry]

• Michael Karr. Summation in finite terms. Journal of the ACM, 28(2):305-350, April 1981. [BibTeX entry]

• R. M. Feldman, G. W. Adkins, G. L. Curry, and U. W. Pooch. Measurement bias in feedback queues. Journal of the ACM, 28(2):351-357, April 1981. [BibTeX entry]

• K. C. Sevcik and I. Mitrani. The distribution of queuing network states at input and output instants. Journal of the ACM, 28(2):358-371, April 1981. Citations. [BibTeX entry]

• C. J. Hogger. Derivation of logic programs. Journal of the ACM, 28(2):372-392, April 1981. Citations. [BibTeX entry]

• Martin Rem. The closure statement: A programming language construct allowing ultraconcurrent execution. Journal of the ACM, 28(2):393-410, April 1981. [BibTeX entry]

• K. J. Lieberherr and E. Specker. Complexity of partial satisfaction. Journal of the ACM, 28(2):411-421, April 1981. Citations. [BibTeX entry]

Volume 28, Number 3, July 1981

• Mark E. Stickel. A unification algorithm for associative-commutative functions. Journal of the ACM, 28(3):423-434, July 1981. Citations. [BibTeX entry]

• Yehoshua Sagiv, Claude Delobel, D. Stott Parker, Jr., and Ronald Fagin. An equivalence between relational database dependencies and a fragment of propositional logic. Journal of the ACM, 28(3):435-453, July 1981. Citations. [BibTeX entry]

• David Dobkin and J. Ian Munro. Optimal time minimal space selection algorithms. Journal of the ACM, 28(3):454-461, July 1981. [BibTeX entry]

• Francis Y. Chin and Long-Lieh Tsai. On J-maximal and J-minimal flow-shop schedules. Journal of the ACM, 28(3):462-476, July 1981. [BibTeX entry]

• Leonard Kleinrock and Arne Nilsson. On optimal scheduling algorithms for time-shared systems. Journal of the ACM, 28(3):477-486, July 1981. Citations. [BibTeX entry]

• Hanan Samet. Connected component labeling using quadtrees. Journal of the ACM, 28(3):487-501, July 1981. Citations. [BibTeX entry]

• Sarangan Krishna Kumar and Melvin A. Breuer. Probabilistic aspects of Boolean switching functions via a new transform. Journal of the ACM, 28(3):502-520, July 1981. [BibTeX entry]

• R. P. Brent and H. T. Kung. The area-time complexity of binary multiplication. Journal of the ACM, 28(3):521-534, July 1981. Citations. [BibTeX entry]

• Eitan M. Gurari and Oscar H. Ibarra. The complexity of the equivalence problem for simple programs. Journal of the ACM, 28(3):535-560, July 1981. [BibTeX entry]

• Ernst W. Mayr and Albert R. Meyer. The complexity of the finite containment problem for Petri nets. Journal of the ACM, 28(3):561-576, July 1981. Citations. [BibTeX entry]

• Robert Endre Tarjan. A unified approach to path problems. Journal of the ACM, 28(3):577-593, July 1981. Citations. [BibTeX entry]

• Robert Endre Tarjan. Fast algorithms for solving path problems. Journal of the ACM, 28(3):594-614, July 1981. Citations. [BibTeX entry]

• Andrew Chi-Chih Yao. Should tables be sorted? Journal of the ACM, 28(3):615-628, July 1981. Citations. [BibTeX entry]

• M. Reiser and S. S. Lavenberg. Corrigendum: ``Mean-value analysis of closed multichain queuing networks''. Journal of the ACM, 28(3):629, July 1981. References. [BibTeX entry]

Volume 28, Number 4, October 1981

• Wolfgang Bibel. On matrices with connections. Journal of the ACM, 28(4):633-645, October 1981. Citations. [BibTeX entry]

• D. W. Loveland and C. R. Reddy. Deleting repeated goals in the problem reduction format. Journal of the ACM, 28(4):646-661, October 1981. [BibTeX entry]

• Guy Latouche. Algorithmic analysis of a multiprogramming-multiprocessor computer system. Journal of the ACM, 28(4):662-679, October 1981. [BibTeX entry]

• David Maier, Yehoshua Sagiv, and Mihalis Yannakakis. On the complexity of testing implications of functional and join dependencies. Journal of the ACM, 28(4):680-695, October 1981. Citations. [BibTeX entry]

• Michael L. Fredman. A lower bound on the complexity of orthogonal range queries. Journal of the ACM, 28(4):696-705, October 1981. Citations. [BibTeX entry]

• A. Ehrenfeucht, G. Rozenberg, and K. Ruohonen. A morphic representation of complements of recursively enumerable sets. Journal of the ACM, 28(4):706-714, October 1981. [BibTeX entry]

• Mehdi Jazayeri. A simpler construction for showing the intrinsically exponential complexity of the circularity problem for attribute grammars. Journal of the ACM, 28(4):715-720, October 1981. Citations. [BibTeX entry]

• Ernest Davis and Jeffrey M. Jaffe. Algorithms for scheduling tasks on unrelated processors. Journal of the ACM, 28(4):721-736, October 1981. Citations. [BibTeX entry]

• Stefania Gnesi, Ugo Montanari, and Alberto Martelli. Dynamic programming as graph searching: An algebraic approach. Journal of the ACM, 28(4):737-751, October 1981. Citations. [BibTeX entry]

• N. Katoh, T. Ibaraki, and H. Mine. An algorithm for the K best solutions of the resource allocation problem. Journal of the ACM, 28(4):752-764, October 1981. [BibTeX entry]

• Christos H. Papadimitriou. On the complexity of integer programming. Journal of the ACM, 28(4):765-768, October 1981. Citations. [BibTeX entry]

• Robert Shostak. Deciding linear inequalities by computing loop residues. Journal of the ACM, 28(4):769-779, October 1981. Citations. [BibTeX entry]

• Andrew Chi-Chih Yao. A lower bound to finding convex hulls. Journal of the ACM, 28(4):780-787, October 1981. Citations. [BibTeX entry]

Shortcuts: