Journal of the ACM, Volume 31, 1984

Volume 31, Number 1, January 1984

• Robert E. Shostak:
  Deciding Combinations of Theories. 1-12
  
• H. James Hoover, Maria M. Klawe, Nicholas Pippenger:
  Bounding Fan-out in Logical Networks. 13-18
  
• Peter Eades, Michael Hickey, Ronald C. Read:
  Some Hamilton Paths and a Minimal Change Algorithm. 19-29
  
• Catriel Beeri, Martin Dowd, Ronald Fagin, Richard Statman:
  On the Structure of Armstrong Relations for Functional Dependencies. 30-46
  
• Lawrence J. Henschen, Shamim A. Naqvi:
  On compiling queries in recursive first-order databases. 47-85
  
• Aurel A. Lazar:
  Optimal Flow Control of an M/M/m Queue. 86-98
  
• Sidnie Dresher Feit:
  A Fast Algorithm for the Two-Variable Integer Programming Problem. 99-113
  
• Nimrod Megiddo:
  Linear Programming in Linear Time When the Dimension Is Fixed. 114-127
  
• Onno J. Boxma, Frank P. Kelly, Alan G. Konheim:
  The Product Form for Sojourn Time Distributions in Cyclic Exponential Queues. 128-133
  
• Burton Simon:
  Priority Queues with Feedback. 134-149
  
• Joseph JáJá, Viktor K. Prasanna:
  Information Transfer in Distributed Computing with Applications to VLSI. 150-162
  
• Douglas R. Smith:
  Random Trees and the Analysis of Branch and Bound Procedures. 163-188
  

Volume 31, Number 2, April 1984

• Allan Gottlieb, Clyde P. Kruskal:
  Complexity Results for Permuting Data and Other Computations on Parallel Processors. 193-209
  
• Richard Hull:
  Finitely Specifiable Implicational Dependency Families. 210-226
  
• Mihalis Yannakakis:
  Serializability by Locking. 227-244
  
• Robert Endre Tarjan, Jan van Leeuwen:
  Worst-case Analysis of Set Union Algorithms. 245-281
  
• Karel Culik II, Tero Harju:
  The omega-Sequence Problem for DOL Systems Is Decidable. 282-298
  
• Harry B. Hunt III:
  Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes. 299-318
  
• C. W. Clenshaw, F. W. J. Olver:
  Beyond Floating Point. 319-328
  
• George M. Trojan:
  Lower Bounds and Fast Algorithms for Sequence Acceleration. 329-335
  
• Hans Röck:
  The Three-Machine No-Wait Flow Shop is NP-Complete. 336-345
  
• James McKenna, Debasis Mitra:
  Asymptotic Expansions and Integral Representations of Moments of Queue Lengths in Closed Markovian Networks. 346-360
  
• Akeo Adachi, Shigeki Iwata, Takumi Kasai:
  Some Combinatorial Game Problems Require Omega(n^k) Time. 361-376
  
• Joseph JáJá:
  The VLSI Complexity of Selected Graph Problems. 377-391
  
• Christos H. Papadimitriou:
  On the complexity of unique solutions. 392-400
  
• John H. Reif:
  Symmetric Complementation. 401-421
  
• John E. Savage:
  Space-Time Trade-Offs for Banded Matrix Problems. 422-437
  

Volume 31, Number 3, July 1984

• Robert S. Boyer, J. Strother Moore:
  A Mechanical Proof of the Unsolvability of the Halting Problem. 441-458
  
• Yuri Gurevich, Larry J. Stockmeyer, Uzi Vishkin:
  Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems. 459-473
  
• François Baccelli, Erol Gelenbe, Brigitte Plateau:
  An End-to-End Approach to the Resequencing Problem. 474-485
  
• Ajoy Kumar Datta, Sukumar Ghosh:
  Synthesis of a Class of Deadlock-Free Petri Nets. 486-506
  
• Eli Upfal:
  Efficient Schemes for Parallel Communication. 507-517
  
• Richard Hull, Chee-Keng Yap:
  The Format Model: A Theory of database Organization. 518-544
  
• Michael L. Fredman, János Komlós, Endre Szemerédi:
  Storing a Sparse Table with 0(1) Worst Case Access Time. 538-544
  
• Joseph F. Traub, Henryk Wozniakowski:
  On the Optimal Solution of Large Linear Systems. 545-559
  
• Stephen D. Brookes, C. A. R. Hoare, A. W. Roscoe:
  A Theory of Communicating Sequential Processes. 560-599
  
• John McLean:
  A Formal Method for the Abstract Specification of Software. 600-627
  
• Micha Hofri:
  Analysis of Interleaved Storage Via a Constant-Service Queuing System with Markov-Chain-Driven Input. 628-648
  
• Mikhail J. Atallah, S. Rao Kosaraju:
  Graph Problems on a Mesh-Connected Processor Array. 649-667
  
• Friedhelm Meyer auf der Heide:
  A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem. 668-676
  

Volume 31, Number 4, October 1984

• S. G. Williamson:
  Depth-First Search and Kuratowski Subgraphs. 681-693
  
• Jonathan W. Greene, Abbas El Gamal:
  Configuration of VLSI Arrays in the Presence of Defects. 694-717
  
• Catriel Beeri, Moshe Y. Vardi:
  A Proof Procedure for Data Dependencies. 718-741
  
• Stavros S. Cosmadakis, Christos H. Papadimitriou:
  Updates of Relational Views. 742-760
  
• Tomasz Imielinski, Witold Lipski Jr.:
  Incomplete Information in Relational Databases. 761-791
  
• Adam W. Bojanczyk:
  Optimal Asynchronous Newton Method for the Solution of Nonlinear Equations. 792-803
  
• Pierre-Jacques Courtois, Pierre Semal:
  Bounds for the Positive Eigenvectors of Nonnegative Matrices and for their Approximations by Decomposition. 804-825
  
• A. Robert Calderbank, Edward G. Coffman Jr., Leopold Flatto:
  Optimum Head Separation in a Disk System with Two Read/Write Heads. 826-838
  
• Benjamin Melamed, Micha Yadin:
  Numerical Computation of Sojourn-Time Distributions in Queuing Networks. 839-854
  
• Debasis Mitra, Peter J. Weinberger:
  Probabilistic Models of Database Locking: Solutions, Computational Algorithms, and Asymptotics. 855-878
  
• Peter A. Bloniarz, Harry B. Hunt III, Daniel J. Rosenkrantz:
  Algebraic Structures with Hard Equivalence and Minimization Problems. 879-904
  
• Jan K. Pachl, Ephraim Korach, Doron Rotem:
  Lower Bounds for Distributed Maximum-Finding Algorithms. 905-918