19. FOCS 1978: Ann Arbor, Michigan, USA

Session I

• Jean Françon, G. Viennot, Jean Vuillemin:
  Description and Analysis of an Efficient Priority Queue Representation. 1-7
  
• Leonidas J. Guibas, Robert Sedgewick:
  A Dichromatic Framework for Balanced Trees. 8-21
  
• Andrew Chi-Chih Yao:
  Should Tables Be Sorted? (Extended Abstract). 22-27
  
• George S. Lueker:
  A Data Structure for Orthogonal Range Queries. 28-34
  
• Harry R. Lewis:
  Complexity of Solvable Cases of the Decision Problem for the Predicate Calculus. 35-47
  
• David Lichtenstein, Michael Sipser:
  GO Is PSPACE Hard. 48-54
  
• Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, Yaacov Yesha:
  The Complexity of Checkers on an N * N Board - Preliminary Report. 55-64
  

Session II

• Juris Hartmanis, Neil Immerman, Stephen R. Mahaney:
  One-Way Log-Tape Reductions. 65-72
  
• Michael Sipser:
  Halting Space-Bounded Computations. 73-74
  
• Leonard M. Adleman:
  Two Theorems on Random Polynomial Time. 75-83
  
• Rüdiger Reischuk:
  Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game (Preliminary Version). 84-91
  
• Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer:
  Alternating Pushdown Automata (Preliminary Report). 92-106
  
• Janos Simon, John Gill, James Hunt:
  On Tape-Bounded Probabilistic Turing Machine Transducers (Extended Abstract). 107-112
  
• Wolfgang J. Paul, Ernst J. Prauß, Rüdiger Reischuk:
  On Alternation (Preliminary Version). 113-122
  

Session III

• Joost Engelfriet, Grzegorz Rozenberg:
  Equality Languages, Fixed Point Languages and Representations of Recursively Enumerable Languages. 123-126
  
• Ashok K. Chandra:
  Computable Nondeterministic Functions. 127-131
  
• Manuel Blum, Dexter Kozen:
  On the Power of the Compass (or, Why Mazes Are Easier to Search than Graphs). 132-142
  
• Imre Simon:
  Limited Subsets of a Free Monoid. 143-150
  
• Harold Abelson:
  Lower Bounds on Information Transfer in Distributed Computations. 151-158
  
• Jean-Paul Van de Wiele:
  An Optimal Lower Bound on the Number of Total Operations to Compute 0-1 Polynomials over the Field of Complex Numbers. 159-165
  
• Victor Y. Pan:
  Strassen's Algorithm Is not Optimal: Trililnear Technique of Aggregating, Uniting and Canceling for Constructing Fast Algorithms for Matrix Operations. 166-176
  

Session IV

• Rohit Parikh:
  A Decidability Result for a Second Order Process Logic. 177-183
  
• Lawrence Flon, Norihisa Suzuki:
  Consistent and Complete Proof Rules for the Total Correctness of Parallel Programs. 184-192
  
• Richard J. Lipton:
  Model Theoretic Aspects of Computational Complexity. 193-200
  
• Bruno Courcelle:
  On Recursive Equations Having a Unique Solution. 201-213
  
• Daniel J. Lehmann:
  On the Algebra of Order (Extended Abstract). 214-220
  
• Akira Kanda:
  Data Types as Initial Algebras: A unification of Scottery and ADJery (Extended Abstract). 221-230
  

Session V

• Zvi Galil:
  A New Algorithm for the Maximal Flow Problem. 231-245
  
• Barbara Simons:
  A Fast Algorithm for Single Processor Scheduling. 246-252
  
• J. Ian Munro, Mike Paterson:
  Selection and Sorting with Limited Storage. 253-258
  
• C. Christen:
  Improving the Bounds on Optimal Merging. 259-266
  
• Chee-Keng Yap:
  On Lifted Problems (Preliminary Reports). 267-279
  
• Andrew Chi-Chih Yao, F. Frances Yao:
  On the Average-case Complexity of Selecting k-th Best. 280-289
  

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