17. FOCS 1976: Houston, Texas, USA

Session I

• Ronald L. Rivest, Vaughan R. Pratt:
  The Mutual Exclusion Problem for Unreliable Processes: Preliminary Report. 1-8
  
• Peter B. Henderson, Yechezkel Zalcstein:
  Characterization of the Synchronization Languages for PV Systems. 9-18
  
• Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz:
  Concurrency Control for Database Systems. 19-32
  
• Anita K. Jones, Richard J. Lipton, Lawrence Snyder:
  A Linear Time Algorithm for Deciding Security. 33-41
  
• Rodney Farrow, Ken Kennedy, Linda Zucconi:
  Graph Grammars and Global Program Data Flow Analysis. 42-56
  
• Peter J. Downey, Ravi Sethi:
  Assignment Commands and Array Structures. 57-66
  

Session II

• Andrew Chi-Chih Yao, Ronald L. Rivest:
  k+1 Heads Are Better than k. 67-70
  
• Theodore P. Baker, Alan L. Selman:
  A Second Step toward the Polynomial Hierarchy. 71-75
  
• Leonard Berman:
  On the Structure of Complete Sets: Almost Everywhere Complexity and Infinitely Often Speedup. 76-80
  
• Leonard M. Adleman, Kenneth L. Manders:
  Diophantine Complexity. 81-88
  
• Dexter Kozen:
  On Parallelism in Turing Machines. 89-97
  
• Ashok K. Chandra, Larry J. Stockmeyer:
  Alternation. 98-108
  

Session III

• Vaughan R. Pratt:
  Semantical Considerations on Floyd-Hoare Logic. 109-121
  
• Daniel J. Lehmann:
  Categories for Fixpoint-Semantics. 122-126
  
• Laurian M. Chirica, David F. Martin:
  An Algebraic Formulation of Knuthian Semantics. 127-136
  
• Bruno Courcelle, Maurice Nivat:
  Algebraic Families of Interpretations. 137-146
  
• Jesse B. Wright, James W. Thatcher, Eric G. Wagner, Joseph A. Goguen:
  Rational Algebraic Theories and Fixed-Point Solutions. 147-158
  
• Emily P. Friedman:
  Simple Languages and Free Schemes. 159-165
  

Session IV

• Brian Allen, J. Ian Munro:
  Self-Organizing Binary Search Trees. 166-172
  
• Andrew Chi-Chih Yao, F. Frances Yao:
  The Complexity of Searching an Ordered Random Table (Extended Abstract). 173-177
  
• Frank Fussenegger, Harold N. Gabow:
  Using Comparison Trees to Derive Lower Bounds for Selection Problems. 178-182
  
• Leonidas J. Guibas:
  The Analysis of Hashing Algorithms that Exhibit k-ary Clustering. 183-196
  
• Douglas Comer, Ravi Sethi:
  Complexity of Trie Index Construction (Extended Abstract). 197-207
  
• Michael Ian Shamos, Dan Hoey:
  Geometric Intersection Problems. 208-215
  
• Greg N. Frederickson, Matthew S. Hecht, Chul E. Kim:
  Approximation Algorithms for some Routing Problems. 216-227
  

Session V

• Jan van Leeuwen:
  Variations of a New Machine Model. 228-235
  
• Zvi Galil, Joel I. Seiferas:
  Recognizing Certain Repetitions and Reversals Within Strings. 236-252
  
• Luc Boasson, Maurice Nivat:
  Parenthesis Generators. 253-257
  

Session VI

• Nicholas Pippenger:
  On the Evaluation of Powers and Related Problems (Preliminary Version). 258-263
  
• David A. Plaisted:
  Some Polynomial and Integer Divisibility Problems Are NP-Hard. 264-267
  
• Michael Ian Shamos, Gideon Yuval:
  Lower Bounds from Complex Function Theory. 268-273
  

Last update Fri May 25 08:14:14 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page