Journal of the ACM, Volume 27, 1980

Volume 27, Number 1, January 1980

• Andrzej Proskurowski:
  On the Generation of Binary Trees. 1-2
  
• Marvin H. Solomon, Raphael A. Finkel:
  A Note on Enumerating Binary Trees. 3-5
  
• David Nassimi, Sartaj Sahni:
  An optimal routing algorithm for mesh-connected Parallel computers. 6-29
  
• Krzysztof Pawlikowski:
  Message Waiting Time in a Packet Switching System. 30-41
  
• G. Boyd Swartz:
  Polling in a Loop System. 42-59
  
• Peter B. Henderson, Yechezkel Zalcstein:
  Synchronization Problems Solvable by Generalized PV Systems. 60-71
  
• Abraham Silberschatz, Zvi M. Kedem:
  Consistency in Hierarchical Database Systems. 72-80
  
• Richard J. Lipton, Arnold L. Rosenberg, Andrew Chi-Chih Yao:
  External Hashing Schemes for Collections of Data Structures. 81-95
  
• Joost Engelfriet, Erik Meineche Schmidt, Jan van Leeuwen:
  Stack Machines and Classes of Nonnested Macro Languages. 96-117
  
• Ravindran Kannan:
  A Polynomial Algorithm for the Two-Variable Integer Programming Problem. 118-122
  
• Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton:
  Space-Time Trade-Offs in Structured Programming: An Improved Combinatorial Embedding Theorem. 123-127
  
• Marc A. Kaplan, Jeffrey D. Ullman:
  A Scheme for the Automatic Inference of Variable Types. 128-145
  
• Bhaskaram Prabhala, Ravi Sethi:
  Efficient Computation of Expressions with Common Subexpressions. 146-163
  
• Mitchell Wand:
  Continuation-Based Program Transformation Strategies. 164-180
  
• Edward A. Bender:
  The Number of Fanout-Free Functions with Various Gates. 181-190
  
• Norihisa Suzuki, David Jefferson:
  Verification Decidability of Presburger Array Programs. 191-205
  

Volume 27, Number 2, April 1980

• Andrew Chi-Chih Yao:
  New Algorithms for Bin Packing. 207-227
  
• Marshall C. Pease, Robert E. Shostak, Leslie Lamport:
  Reaching Agreement in the Presence of Faults. 228-234
  
• Raymond Reiter:
  Equality and Domain Closure in First-Order Databases. 235-249
  
• Yehoshua Sagiv:
  An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic. 250-262
  
• Grzegorz W. Wasilkowski:
  Can Any Stationary Iteration Using Linear Information Be Globally Convergent?. 263-269
  
• Tiko Kameda:
  Testing Deadlock-Freedom of Computer Systems. 270-280
  
• We-Min Chow:
  The Cycle Time Distribution of Exponential Cyclic Queues. 281-286
  
• Teofilo F. Gonzalez, Donald B. Johnson:
  A New Algorithm for Preemptive Scheduling of Trees. 287-312
  
• Martin Reiser, Stephen S. Lavenberg:
  Mean-Value Analysis of Closed Multichain Queuing Networks. 313-322
  
• Donald F. Towsley:
  Queuing Network Models with State-Dependent Routing. 323-337
  
• Ramachandran Krishnaswamy, Arthur B. Pyster:
  On the Correctness of Semantic-Syntax-Directed Translations. 338-355
  
• Greg Nelson, Derek C. Oppen:
  Fast Decision Procedures Based on Congruence Closure. 356-364
  
• Stephen A. Ward, Robert H. Halstead Jr.:
  A Syntactic Theory of Message Passing. 365-383
  
• Harold Abelson:
  Lower Bounds on Information Transfer in Distributed Computations. 384-392
  
• David Lichtenstein, Michael Sipser:
  GO Is Polynomial-Space Hard. 393-401
  
• Rainer Parchmann:
  Corrigendum: ``Control System Model for Critically Timed Success''. 402
  

Volume 27, Number 3, July 1980

• Derek C. Oppen:
  Reasoning About Recursively Defined Data Structures. 403-411
  
• Doris Altenkamp, Kurt Mehlhorn:
  Codes: Unequal Probabilities, Unequal Letter Cost. 412-427
  
• Ronald L. Graham, Andrew Chi-Chih Yao, F. Frances Yao:
  Information Bounds Are Weak in the Shortest Distance Problem. 428-444
  
• Yossi Shiloach:
  A Polynomial Solution to the Undirected Two Paths Problem. 445-456
  
• Kishor S. Trivedi, Robert A. Wagner, Timothy M. Sigmon:
  Optimal Selection of CPU Speed, Device Capacities, and File Assignments. 457-473
  
• Haim Mendelson, Uri Yechiali:
  A New Approach to the Analysis of Linear Probing Schemes. 474-483
  
• Fred G. Abramson, Yuri Breitbart, Forbes D. Lewis:
  Complex Properties of Grammars. 484-498
  
• Joost Engelfriet, Grzegorz Rozenberg:
  Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages. 499-518
  
• Guy Fayolle, Isi Mitrani, R. Iasnogorodski:
  Sharing a Processor Among Many Job Classes. 519-532
  
• Christos H. Papadimitriou, Paris C. Kanellakis:
  Flowshop scheduling with limited temporary storage. 533-549
  
• Sartaj Sahni, Yookun Cho:
  Scheduling Independent Tasks with Due Times on a Uniform Processor System. 550-563
  
• Carlo Ghezzi, Dino Mandrioli:
  Augmenting Parsers to Support Incrementality. 564-579
  
• Ravi Sethi, Adrian Tang:
  Constructing Call-by-Value Continuation Semantics. 580-597
  

Volume 27, Number 4, October 1980

• Alan R. Aronson, Barry E. Jacobs, Jack Minker:
  A Note on Fuzzy Deduction. 599-603
  
• D. T. Lee:
  Two-Dimensional Voronoi Diagrams in the L_p-Metric. 604-618
  
• Shuji Tsukiyama, Isao Shirakawa, Hiroshi Ozaki, Hiromu Ariyoshi:
  An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset. 619-632
  
• Yehoshua Sagiv, Mihalis Yannakakis:
  Equivalences Among Relational Expressions with the Union and Difference Operators. 633-655
  
• Andrzej Ehrenfeucht, Grzegorz Rozenberg:
  The Sequence Equivalence Problem is Decidable for 0S Systems. 656-663
  
• David Maier:
  Minimum Covers in Relational Database Model. 664-674
  
• Sheila A. Greibach, Emily P. Friedman:
  Superdeterministic PDAs: A Subcase with a Decidable Inclusion problem. 675-700
  
• Jacob T. Schwartz:
  Fast Probabilistic Algorithms for Verification of Polynomial Identities. 701-717
  
• Marshall L. Fisher, Dorit S. Hochbaum:
  Database Location in Computer Networks. 718-735
  
• K. G. Ramakrishnan:
  Solving Two-Commodity Transportation Problems with Coupling Constraints. 736-757
  
• Peter J. Downey, Ravi Sethi, Robert Endre Tarjan:
  Variations on the Common Subexpression Problem. 758-771
  
• Jean-Claude Raoult, Jean Vuillemin:
  Operational and Semantic Equivalence Between Recursive Programs. 772-796
  
• Gérard P. Huet:
  Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems. 797-821
  
• Joseph JáJá:
  Computations of Bilinear Forms over Finite Fields. 822-830
  
• Richard E. Ladner, Michael J. Fischer:
  Parallel Prefix Computation. 831-838
  
• Rüdiger Reischuk:
  Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game. 839-849