Journal of the ACM -- 1980

Volume 27, Number 1, January 1980

• Andrzej Proskurowski. On the generation of binary trees. Journal of the ACM, 27(1):1-2, January 1980. Citations. [BibTeX entry]

• Marvin Solomon and Raphael A. Finkel. A note on enumerating binary trees. Journal of the ACM, 27(1):3-5, January 1980. Citations. [BibTeX entry]

• David Nassimi and Sartaj Sahni. An optimal routing algorithm for mesh-connected parallel computers. Journal of the ACM, 27(1):6-29, January 1980. Citations. [BibTeX entry]

• Krzysztof Pawlikowski. Message waiting time in a packet switching system. Journal of the ACM, 27(1):30-41, January 1980. [BibTeX entry]

• G. Boyd Swartz. Polling in a loop system. Journal of the ACM, 27(1):42-59, January 1980. [BibTeX entry]

• Peter B. Henderson and Yechezkel Zalcstein. Synchronization problems solvable by generalized PV systems. Journal of the ACM, 27(1):60-71, January 1980. [BibTeX entry]

• Abraham Silberschatz and Zvi Kedem. Consistency in hierarchical database systems. Journal of the ACM, 27(1):72-80, January 1980. Citations. [BibTeX entry]

• Richard J. Lipton, Arnold L. Rosenberg, and Andrew C. Yao. External hashing schemes for collections of data structures. Journal of the ACM, 27(1):81-95, January 1980. [BibTeX entry]

• Joost Engelfriet, Erik Meineche Schmidt, and Jan van Leeuwen. Stack machines and classes of nonnested macro languages. Journal of the ACM, 27(1):96-117, January 1980. Citations. [BibTeX entry]

• Ravindran Kannan. A polynomial algorithm for the two-variable integer programming problem. Journal of the ACM, 27(1):118-122, January 1980. Citations. [BibTeX entry]

• Ricard A. DeMillo, Stanley C. Eisenstat, and Richard J. Lipton. Space-time trade-offs in structured programming: An improved combinatorial embedding theorem. Journal of the ACM, 27(1):123-127, January 1980. [BibTeX entry]

• Marc A. Kaplan and Jeffrey D. Ullman. A scheme for the automatic inference of variable types. Journal of the ACM, 27(1):128-145, January 1980. Citations. [BibTeX entry]

• Bhaskaram Prabhala and Ravi Sethi. Efficient computation of expressions with common subexpressions. Journal of the ACM, 27(1):146-163, January 1980. [BibTeX entry]

• Mitchell Wand. Continuation-based program transformation strategies. Journal of the ACM, 27(1):164-180, January 1980. Citations. [BibTeX entry]

• Edward A. Bender. The number of fanout-free functions with various gates. Journal of the ACM, 27(1):181-190, January 1980. [BibTeX entry]

• Norihisa Suzuki and David Jefferson. Verification decidability of Presburger array programs. Journal of the ACM, 27(1):191-205, January 1980. [BibTeX entry]

Volume 27, Number 2, April 1980

• Andrew Chi-Chih Yao. New algorithms for bin packing. Journal of the ACM, 27(2):207-227, April 1980. Citations. [BibTeX entry]

• M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, April 1980. Citations. [BibTeX entry]

• Raymond Reiter. Equality and domain closure in first-order databases. Journal of the ACM, 27(2):235-249, April 1980. Citations. [BibTeX entry]

• Yehoshua Sagiv. An algorithm for inferring multivalued dependencies with an application to propositional logic. Journal of the ACM, 27(2):250-262, April 1980. [BibTeX entry]

• G. W. Wasilkowski. Can any stationary iteration using linear information be globally convergent? Journal of the ACM, 27(2):263-269, April 1980. Citations. [BibTeX entry]

• Tiko Kameda. Testing deadlock-freedom of computer systems. Journal of the ACM, 27(2):270-280, April 1980. Citations. [BibTeX entry]

• We-Min Chow. The cycle time distribution of exponential cyclic queues. Journal of the ACM, 27(2):281-286, April 1980. [BibTeX entry]

• Teofilo F. Gonzalez and Donald B. Johnson. A new algorithm for preemptive scheduling of trees. Journal of the ACM, 27(2):287-312, April 1980. Citations. [BibTeX entry]

• M. Reiser and S. S. Lavenberg. Mean-value analysis of closed multichain queuing networks. Journal of the ACM, 27(2):313-322, April 1980. Citations. [BibTeX entry]

• Don Towsley. Queuing network models with state-dependent routing. Journal of the ACM, 27(2):323-337, April 1980. Citations. [BibTeX entry]

• Ramachandran Krishnaswamy and Arthur B. Pyster. On the correctness of semantic-syntax-directed translations. Journal of the ACM, 27(2):338-355, April 1980. [BibTeX entry]

• Greg Nelson and Derek C. Oppen. Fast decision procedures based on congruence closure. Journal of the ACM, 27(2):356-364, April 1980. Citations. [BibTeX entry]

• Stephen A. Ward and Robert H. Halstead, Jr.. A syntactic theory of message passing. Journal of the ACM, 27(2):365-383, April 1980. [BibTeX entry]

• Harold Abelson. Lower bounds on information transfer in distributed computations. Journal of the ACM, 27(2):384-392, April 1980. Citations. [BibTeX entry]

• David Lichtenstein and Michael Sipser. GO is polynomial-space hard. Journal of the ACM, 27(2):393-401, April 1980. Citations. [BibTeX entry]

• Rainer Parchmann. Corrigendum: ``Control system model for critically timed success''. Journal of the ACM, 27(2):402, April 1980. References. [BibTeX entry]

Volume 27, Number 3, July 1980

• Derek C. Oppen. Reasoning about recursively defined data structures. Journal of the ACM, 27(3):403-411, July 1980. Citations. [BibTeX entry]

• Doris Altenkamp and Kurt Mehlhorn. Codes: Unequal probabilities, unequal letter cost. Journal of the ACM, 27(3):412-427, July 1980. Citations. [BibTeX entry]

• Ronald L. Graham, Andrew C. Yao, and F. Frances Yao. Information bounds are weak in the shortest distance problem. Journal of the ACM, 27(3):428-444, July 1980. Citations. [BibTeX entry]

• Yossi Shiloach. A polynomial solution to the undirected two paths problem. Journal of the ACM, 27(3):445-456, July 1980. Citations. [BibTeX entry]

• Kishor S. Trivedi, Robert A. Wagner, and Timothy M. Sigmon. Optimal selection of CPU speed, device capacities, and file assignments. Journal of the ACM, 27(3):457-473, July 1980. [BibTeX entry]

• Haim Mendelson and Uri Yechiali. A new approach to the analysis of linear probing schemes. Journal of the ACM, 27(3):474-483, July 1980. Citations. [BibTeX entry]

• Fred G. Abramson, Yuri Breitbart, and Forbes D. Lewis. Complex properties of grammars. Journal of the ACM, 27(3):484-498, July 1980. [BibTeX entry]

• J. Engelfriet and G. Rozenberg. Fixed point languages, equality languages, and representation of recursively enumerable languages. Journal of the ACM, 27(3):499-518, July 1980. Citations. [BibTeX entry]

• G. Fayolle, I. Mitrani, and R. Iasnogorodski. Sharing a processor among many job classes. Journal of the ACM, 27(3):519-532, July 1980. [BibTeX entry]

• Christos H. Papadimitriou and Paris C. Kanellakis. Flowshop scheduling with limited temporary storage. Journal of the ACM, 27(3):533-549, July 1980. [BibTeX entry]

• Sartaj Sahni and Yookun Cho. Scheduling independent tasks with due times on a uniform processor system. Journal of the ACM, 27(3):550-563, July 1980. [BibTeX entry]

• Carlo Ghezzi and Dino Mandrioli. Augmenting parsers to support incrementality. Journal of the ACM, 27(3):564-579, July 1980. [BibTeX entry]

• Ravi Sethi and Adrian Tang. Constructing call-by-value continuation semantics. Journal of the ACM, 27(3):580-597, July 1980. [BibTeX entry]

Volume 27, Number 4, October 1980

• Alan R. Aronson, Barry E. Jacobs, and Jack Minker. A note on fuzzy deduction. Journal of the ACM, 27(4):599-603, October 1980. [BibTeX entry]

• D. T. Lee. Two-dimensional Voronoi diagrams in the L_p-metric. Journal of the ACM, 27(4):604-618, October 1980. Citations. [BibTeX entry]

• S. Tsukiyama, I. Shirakawa, H. Ozaki, and H. Ariyoshi. An algorithm to enumerate all cutsets of a graph in linear time per cutset. Journal of the ACM, 27(4):619-632, October 1980. Citations. [BibTeX entry]

• Yehoshua Sagiv and Mihalis Yannakakis. Equivalences among relational expressions with the union and difference operators. Journal of the ACM, 27(4):633-655, October 1980. Citations. [BibTeX entry]

• A. Ehrenfeucht and G. Rozenberg. The sequence equivalence problem is decidable for 0S systems. Journal of the ACM, 27(4):656-663, October 1980. [BibTeX entry]

• David Maier. Minimum covers in relational database model. Journal of the ACM, 27(4):664-674, October 1980. [BibTeX entry]

• S. A. Greibach and E. P. Freidman. Superdeterministic PDAs: A subcase with a decidable inclusion problem. Journal of the ACM, 27(4):675-700, October 1980. [BibTeX entry]

• J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701-717, October 1980. Citations. [BibTeX entry]

• Marshall L. Fisher and Dorit S. Hochbaum. Database location in computer networks. Journal of the ACM, 27(4):718-735, October 1980. Citations. [BibTeX entry]

• K. G. Ramakrishnan. Solving two-commodity transportation problems with coupling constraints. Journal of the ACM, 27(4):736-757, October 1980. [BibTeX entry]

• Peter J. Downey, Ravi Sethi, and Robert Endre Tarjan. Variations on the common subexpression problem. Journal of the ACM, 27(4):758-771, October 1980. Citations. [BibTeX entry]

• Jean-Claude Raoult and Jean Vuillemin. Operational and semantic equivalence between recursive programs. Journal of the ACM, 27(4):772-796, October 1980. Citations. [BibTeX entry]

• Gérard Huet. Confluent reductions: Abstract properties and application to term rewriting systems. Journal of the ACM, 27(4):797-821, October 1980. Citations. [BibTeX entry]

• Joseph Ja' Ja'. Computations of bilinear forms over finite fields. Journal of the ACM, 27(4):822-830, October 1980. Citations. [BibTeX entry]

• Richard E. Ladner and Michael J. Fischer. Parallel prefix computation. Journal of the ACM, 27(4):831-838, October 1980. Citations. [BibTeX entry]

• Rüdiger Reischuk. Improved bounds on the problem of time-space trade-off in the pebble game. Journal of the ACM, 27(4):839-849, October 1980. Citations. [BibTeX entry]

Shortcuts: