Journal of the ACM, Volume 25, 1978

Volume 25, Number 1, January 1978

• Yehoshua Perl, Yossi Shiloach:
  Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph. 1-9
  
• Luigi Logrippo:
  Renamings and Economy of Memory in Program Schemata. 10-22
  
• Ronald V. Book:
  Simple Representations of Certain Classes of Languages. 23-31
  
• Harry B. Hunt III, Thomas G. Szymanski:
  Lower Bounds and Reductions Between Grammar Problems. 32-51
  
• R. Attar, Yaacov Choueka, Nachum Dershowitz, Aviezri S. Fraenkel:
  KEDMA - Linguistic Tools for Retrieval Systems. 52-66
  
• William S. Cooper, M. E. Maron:
  Foundations of Probabilistic and Utility-Theoretic Indexing. 67-80
  
• Ahmed H. Sameh, David J. Kuck:
  On Stable Parallel Linear System Solvers. 81-91
  
• Teofilo F. Gonzalez, Sartaj Sahni:
  Preemptive Scheduling of Uniform Processor Systems. 92-101
  
• Zvi Galil, Joel I. Seiferas:
  A Linear-Time On-Line Recognition Algorithm for ``Palstar''. 102-111
  
• W. Morven Gentleman:
  Some Complexity Results for Matrix Computations on Parallel Processors. 112-115
  
• Oscar H. Ibarra:
  Reversal-Bounded Multicounter Machines and Their Decision Problems. 116-133
  
• Harry R. Lewis:
  Renaming a Set of Clauses as a Horn Set. 134-135
  
• Claus-Peter Schnorr:
  Satisfiability Is Quasilinear Complete in NQL. 136-145
  
• Joel I. Seiferas, Michael J. Fischer, Albert R. Meyer:
  Separating Nondeterministic Time Complexity Classes. 146-167
  
• Mitchell Wand:
  A New Incompleteness Result for Hoare's System. 168-175
  

Volume 25, Number 2, April 1978

• Edward C. Horvath:
  Stable Sorting in Asymptotically Optimal Time and Extra Space. 177-199
  
• Ronald L. Rivest:
  Optimal Arrangement of Keys in a Hash Table. 200-209
  
• Clement T. Yu, Gerard Salton, M. K. Siu:
  Effective Automatic Indexing Using Term Addition and Deletion. 210-225
  
• Gérard M. Baudet:
  Asynchronous Iterative Methods for Multiprocessors. 226-244
  
• H. T. Kung, J. F. Traub:
  All Algebraic Functions Can Be Computed Fast. 245-260
  
• William McKie:
  An Example of a Skewing Function. 261-265
  
• John M. Mulvey:
  Pivot Strategies for Primal-Simplex Network Codes. 266-270
  
• David R. Musser:
  On the Efficiency of a Polynomial Irreducibility Test. 271-282
  
• Kenneth J. Omahen, V. Marathe:
  Analysis and Applications of the Delay Cycle for the M/M/c Queueing System. 283-303
  
• Andris A. Zoltners:
  A Direct Descent Binary Knapsack Algorithm. 304-311
  
• Neil D. Jones, Steven S. Muchnick:
  The Complexity of Finite Memory Programs with Recursion. 312-321
  
• David Maier:
  The Complexity of Some Problems on Subsequences and Supersequences. 322-336
  
• Andrew Chi-Chih Yao, Ronald L. Rivest:
  k+1 Heads Are Better than k. 337-340
  

Volume 25, Number 3, July 1978

• Malcolm C. Harrison, Norman Rubin:
  Another Generalization of Resolution. 341-351
  
• Lawrence H. Landweber, Edward L. Robertson:
  Properties of Conflict-Free and Persistent Petri Nets. 352-364
  
• Dennis G. Kafura, V. Y. Shen:
  An Algorithm to Design the Memory Configuration of a Computer Network. 365-377
  
• Gururaj S. Rao:
  Performance Analysis of Cache Memories. 378-395
  
• Doron Rotem, Yaakov L. Varol:
  Generation of Binary Trees from Ballot Sequences. 396-404
  
• Ivan Hal Sudborough:
  On the Tape Complexity of Deterministic Context-Free Languages. 405-414
  
• Herbert S. Wilf:
  A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane. 415-420
  
• A. C. McKellar, C. K. Wong:
  Dynamic Placement of Records in Linear Storage. 421-434
  
• Robert S. Garfinkel, K. C. Gilbert:
  The Bottleneck Traveling Salesman Problem: Algorithms and Probabilistic Analysis. 435-448
  
• Donald L. Iglehart, Gerald S. Shedler:
  Regenerative Simulation of Response Times in Networks of Queues. 449-460
  
• C. A. R. Hoare:
  Some Properties of Predicate Transformers. 461-480
  
• Jon T. Butler:
  Analysis and Design of Fanout-Free Networks of Positive Symmetric Gates. 481-498
  
• M. R. Garey, David S. Johnson:
  ``Strong'' NP-Completeness Results: Motivation, Examples, and Implications. 499-508
  
• Nicholas Pippenger:
  A Time-Space Trade-Off. 509-515
  

Volume 25, Number 4, October 1978

• Alon Itai, Michael Rodeh, Steven L. Tanimoto:
  Some Matching Problems for Bipartite Graphs. 517-525
  
• Brian Allen, J. Ian Munro:
  Self-Organizing Binary Search Trees. 526-535
  
• Jon Louis Bentley, H. T. Kung, Mario Schkolnick, Clark D. Thompson:
  On the Average Number of Maxima in a Set of Vectors and Applications. 536-543
  
• Leonidas J. Guibas:
  The Analysis of Hashing Techniques That Exhibit k-ary Clustering. 544-555
  
• Donald B. Johnson, Samuel D. Kashdan:
  Lower Bounds for Selection in X+Y and Other Multisets. 556-570
  
• Stefano Crespi-Reghizzi, Giovanni Guida, Dino Mandrioli:
  Noncounting Context-Free Languages. 571-580
  
• Richard P. Brent, H. T. Kung:
  Fast Algorithms for Manipulating Formal Power Series. 581-595
  
• Alon Itai:
  Two-Commodity Flow. 596-611
  
• Eugene L. Lawler, Jacques Labetoulle:
  On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming. 612-619
  
• Hendrik Vantilborgh:
  Exact Aggregation in Exponential Queueing Networks. 620-629
  
• Daniel Brand:
  Path Calculus in Program Verification. 630-651
  
• Peter J. Downey, Ravi Sethi:
  Assignment Commands with Array References. 652-666
  
• Ravi Sethi:
  Conditional Expressions with Equality Tests. 667-674
  
• Alexis C. Arvillias, Dimitris G. Maritsas:
  Partitioning the Period of a Class of m-Sequences and Application to Pseudorandom Number Generation. 675-686
  
• Harry B. Hunt III, Thomas G. Szymanski:
  Corrigendum: ``Lower Bounds and Reductions Between Grammar Problems''. 687-688