Journal of the ACM, Volume 30, 1983

Volume 30, Number 1, January 1983

• A. Bagchi, A. Mahanti:
  Search Algorithms Under Different Kinds of Heuristics-A Comparative Study. 1-21
  
• Dennis de Champeaux:
  Bidirectional Heuristic Search Again. 22-32
  
• Dilip V. Sarwate:
  A Note on ``A Note on Multiple Error Detection in ASCII Numeric Data Communication''. 33-35
  
• Anthony C. Klug:
  Locking Expressions for Increased Database Concurrency. 36-54
  
• Henry F. Korth:
  Locking Primitives in a Database System. 55-79
  
• Greg N. Frederickson:
  Implicit Data Structures for the Dictionary Problem. 80-94
  
• Hermann A. Maurer, Arto Salomaa, Derick Wood:
  A Supernormal-Form Theorem for Context-Free Grammars. 95-102
  
• R. E. Lord, J. S. Kowalik, S. P. Kumar:
  Solving Linear Algebraic Equations on an MIMD Computer. 103-117
  
• Bezalel Gavish:
  Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem. 118-132
  
• Ravindran Kannan:
  Polynomial-Time Aggregation of Integer Programming Problems. 133-145
  
• Rolf Schassberger, Hans Daduna:
  The Time for a Round Trip in a Cycle of Exponential Queues. 146-150
  
• Steven Fortune, Daniel Leivant, Michael O'Donnell:
  The Expressiveness of Simple and Second-Order Type Structures. 151-185
  
• H. Raymond Strong:
  Vector Execution of Flow Graphs. 186-196
  
• Krzysztof R. Apt:
  Formal Justification of a Proof System for Communicating Sequential Processes. 197-216
  
• Oscar H. Ibarra, Shlomo Moran:
  Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs. 217-228
  

Volume 30, Number 2, April 1983

• Jeffrey Scott Vitter:
  Analysis of the Search Performance of Coalesced Hashing. 231-258
  
• Seppo Sippu, Eljas Soisalon-Soininen, Esko Ukkonen:
  The Complexity of LALR(k) Testing. 259-270
  
• G. W. Stewart:
  Computable Error Bounds for Aggregated Markov Chains. 271-285
  
• K. Mani Chandy, Alain J. Martin:
  A Characterization of Product-Form Queuing Networks. 286-299
  
• Jeffrey M. Jaffe:
  Decentralized Simulation of Resource Managers. 300-322
  
• Daniel Brand, Pitro Zafiropulo:
  On Communicating Finite-State Machines. 323-342
  
• Cyrus F. Nourani:
  Abstract Implementations and Their Correctness Proofs. 343-359
  
• Zvi Galil, Wolfgang J. Paul:
  An Efficient General-Purpose Parallel Computer. 360-387
  

Volume 30, Number 3, July 1983

• Michael Tarsi:
  Optimal Search on Some Game Trees. 389-396
  
• Arnold L. Rosenberg:
  Three-Dimensional VLSI: A Case Study. 397-416
  
• David W. Matula, Leland L. Beck:
  Smallest-Last Ordering and clustering and Graph Coloring Algorithms. 417-427
  
• Kenneth J. Supowit:
  The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees. 428-448
  
• Eshrat Arjomandi, Michael J. Fischer, Nancy A. Lynch:
  Efficiency of Synchronous Versus Asynchronous Distributed Systems. 449-456
  
• Edward G. Coffman Jr., Ravi Sethi:
  Instruction Sets for Evaluating Arithmetic Expressions. 457-478
  
• Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis:
  On the Desirability of Acyclic Database Schemes. 479-513
  
• Ronald Fagin:
  Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. 514-550
  
• Dan Gusfield:
  Parametric Combinatorial Computing and a Problem of Program Module Distribution. 551-563
  
• Rajan Suri:
  Robustness of Queuing Network Formulas. 564-594
  
• Jean-Claude Raoult, Ravi Sethi:
  Properties of a Notation for Combining Functions. 595-611
  
• Edmund M. Clarke, Steven M. German, Joseph Y. Halpern:
  Effective Axiomatizations of Hoare Logics. 612-636
  
• Georg Gati:
  The Complexity of Solving Polynomial Equations by Quadrature. 637-640
  
• Oscar H. Ibarra, Brian S. Leininger:
  On the Simplification and Equivalence Problems for Straight-Line Programs. 641-656
  
• Joseph JáJá:
  Time-Space Trade-offs for Some Algebraic Problems. 657-667
  
• Leslie Lamport:
  The Weak Byzantine Generals Problem. 668-676
  
• Xu Mei-Rui, John E. Donner, Ronald V. Book:
  Refining Nondeterminism in Relativizations of Complexity Classes. 677-685
  

Volume 30, Number 4, October 1983

• Dana S. Nau:
  Decision Quality As a Function of Search Depth on Game Trees. 687-708
  
• Jia-Wei Hong, Kurt Mehlhorn, Arnold L. Rosenberg:
  Cost Trade-offs in Graph Embeddings, with Applications. 709-728
  
• Avi Wigderson:
  Improving the Performance Guarantee for Approximate Graph Coloring. 729-735
  
• Toshihide Ibaraki, Hussein M. Abdel-Wahab, Tiko Kameda:
  Design of Minimum-Cost Deadlock-Free Systems. 736-751
  
• Giorgio Ausiello, Alessandro D'Atri, Domenico Saccà:
  Graph Algorithms for Functional Dependency Manipulation. 752-766
  
• Nathan Goodman, Oded Shmueli:
  Syntactic Characterization of Tree Database Schemas. 767-786
  
• Zvi M. Kedem, Abraham Silberschatz:
  Locking Protocols: From Exclusive to Shared Locks. 787-804
  
• Per-Åke Larson:
  Analysis of Uniform Hashing. 805-819
  
• Yael Krevner, Amiram Yehudai:
  An Iteration Theorem for Simple Precedence Languages. 820-833
  
• Bruce Hajek:
  The Proof of a Folk Theorem on Queuing Delay with Applications to Routing in Networks. 834-851
  
• Nimrod Megiddo:
  Applying Parallel Computation Algorithms in the Design of Serial Algorithms. 852-865