6. STOC 1974: Seattle, Washington, USA

• Ashok K. Chandra:
  Degrees of Translatability and Canonical Forms in Program Schemas: Part I. 1-12
  
• Bruno Courcelle, Jean Vuillemin:
  Semantics and Axiomatics of a Simple Recursive Language. 13-26
  
• Leslie G. Valiant:
  The Decidability of Equivalence for Deterministic Finite-Turn Pushdown Automata. 27-32
  
• Stephen A. Cook, Ravi Sethi:
  Storage Requirements for Deterministic Polynomial Time Recognizable Languages. 33-39
  
• Neil D. Jones, William T. Laaser:
  Complete Problems for Deterministic Polynomial Time. 40-46
  
• M. R. Garey, David S. Johnson, Larry J. Stockmeyer:
  Some Simplified NP-Complete Problems. 47-63
  
• Harry B. Hunt III, Daniel J. Rosenkrantz:
  Computational Parallels between the Regular and Context-Free Languages. 64-74
  
• Andrzej Ehrenfeucht, H. Paul Zeiger:
  Complexity Measures for Regular Expressions. 75-79
  
• Vaughan R. Pratt:
  The Power of Negative Thinking in Multiplying Boolean Matrices. 80-83
  
• David G. Kirkpatrick:
  Determining Graph Properties from Matrix Representations. 84-90
  
• John T. Gill III:
  Computational Complexity of Probabilistic Turing Machines. 91-95
  
• Kurt Mehlhorn:
  Polynomial and Abstract Subrecursive Classes. 96-109
  
• Richard E. Ladner, Nancy A. Lynch, Alan L. Selman:
  Comparisons of Polynomial-Time Reducibilities. 110-121
  
• Vaughan R. Pratt, Michael O. Rabin, Larry J. Stockmeyer:
  A Characterization of the Power of Vector Machines. 122-134
  
• Stephen A. Cook, Robert A. Reckhow:
  On the Lengths of Proofs in the Propositional Calculus (Preliminary Version). 135-148
  
• Charles Rackoff:
  On the Complexity of the Theories of Weak Direct Products: A Preliminary Report. 149-160
  
• Edward L. Robertson:
  Structure of Complexity in the Weak Monadic Second-Order Theories of the Natural Numbers. 161-171
  
• John E. Hopcroft, J. K. Wong:
  Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report). 172-184
  
• Robert Endre Tarjan:
  Testing Graph Connectivity. 185-193
  
• Edward C. Horvath:
  Efficient Stable Sorting with Minimal Extra Space. 194-215
  
• Laurent Hyafil, F. Prusker, Jean Vuillemin:
  An Efficient Algorithm for Computing Optimal Desk Merge Patterns (Extended Abstract). 216-229
  
• Richard J. Lipton:
  Limitations of Synchronization Primitives with Conditional Branching and Global Variables. 230-241
  
• Jonathan K. Millen:
  Construction with Parallel Derivatives of the Closure of a Parallel Program Schema. 242-247
  
• K. Vairavan, Richard A. DeMillo:
  Parallel Scheduling of Programs in a Restricted Model of Computation. 248-255
  
• Sheila A. Greibach:
  Some Restrictions on W-Grammars. 256-265
  
• Michael Hammer:
  A New Grammatical Transformation into LL(k) Form (Extended Abstract). 266-275
  
• Joel I. Seiferas:
  Observations on Nondeterministic Multidimensional Iterative Arrays. 276-289
  
• Ronald V. Book, Maurice Nivat, Mike Paterson:
  Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract). 290-296
  
• Arnold L. Rosenberg:
  Managing Storage for Extendible Arrays. 297-302
  
• Jan van Leeuwen:
  A Partial Solution to the Reachability-Problem for Vector-Addition Systems. 303-309
  
• David P. Dobkin, Richard J. Lipton:
  On Some Generalizations of Binary Search. 310-316
  
• Webb Miller:
  Computational Complexity and Numerical Stability. 317-322
  
• H. T. Kung:
  New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions. 323-333
  
• Zvi M. Kedem:
  Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on the Number of Multiplications. 334-341
  
• Allan Borodin, Stephen A. Cook:
  On the Number of Additions to Compute Specific Polynomials (Preliminary Version). 342-347
  

Last update Tue Feb 14 04:11:48 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page