12. STOC 1980: Los Angeles, California, USA

• Albert R. Meyer, Rohit Parikh:
  Definability in Dynamic Logic. 1-7
  
• John H. Reif:
  Logics for Probabilistic Programming (Extended Abstract). 8-13
  
• Grazyna Mirkowska:
  Complete Axiomatization of Algorithmic Properties of Program Schemes with Bounded Nondeterministic Interpretations. 14-21
  
• Vaughan R. Pratt:
  Dynamic Algebras and the Nature of Induction. 22-28
  
• Esko Ukkonen:
  A Decision Method for the Equivalence of some Non-Real-Time Deterministic Pushdown Automata. 29-38
  
• David A. Plaisted:
  On the Distribution of Independent Formulae of Number Theory. 39-44
  
• Richard A. DeMillo, Richard J. Lipton:
  The Consistency of "P = NP" and Related Problems with Fragments of Number Theory. 45-57
  
• Deborah Joseph, Paul Young:
  Independence Results in Computer Science? (Preliminary Version). 58-69
  
• Nancy A. Lynch:
  Fast Allocation of Nearby Resources in a Distributed System. 70-81
  
• Dana Angluin:
  Local and Global Properties in Networks of Processors (Extended Abstract). 82-93
  
• Sam Toueg:
  Deadlock- and Livelock-Free Packet Switching Networks. 94-99
  
• Donna J. Brown:
  Kraft Storage and Access for List Implementations (Extended Abstract). 100-107
  
• H. Raymond Strong:
  Vector Execution of Flow Graphs (Extended Abstract). 108-116
  
• Fereidoon Sadri, Jeffrey D. Ullman:
  A Complete Axiomatization for a Large Class of Dependencies in Relational Databases. 117-122
  
• Ronald Fagin:
  Horn Clauses and Database Dependencies (Extended Abstract). 123-134
  
• Mark H. Overmars, Jan van Leeuwen:
  Dynamically Maintaining Configurations in the Plane (Detailed Abstract). 135-145
  
• Bernard Chazelle, David P. Dobkin:
  Detection is Easier than Computation (Extended Abstract). 146-153
  
• Leonidas J. Guibas, F. Frances Yao:
  On Translating a Set of Rectangles. 154-160
  
• Martin Tompa:
  An Optimal Solution to a Wire-Routing Problem (Preliminary Version). 161-176
  
• Michael J. Fischer, Mike Paterson:
  Optimal Tree Layout (Preliminary Version). 177-189
  
• Richard P. Brent, H. T. Kung:
  The Chip Complexity of Binary Arithmetic. 190-200
  
• James A. Storer:
  The Node Cost Measure for Embedding Graphs on the Planar Grid (Extended Abstract). 201-210
  
• Allen Cypher:
  An Approach to The k Paths Problem. 211-217
  
• David Lichtenstein:
  Isomorphism for Graphs Embeddable on the Projective Plane. 218-224
  
• Gary L. Miller:
  Isomorphism Testing for Graphs of Bounded Genus. 225-235
  
• I. S. Filotti, Jack N. Mayer:
  A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus (Working Paper). 236-243
  
• Christoph M. Hoffmann:
  Testing Isomorphism on Cone Graphs (Extended Abstract). 244-251
  
• Ravindran Kannan, Richard J. Lipton:
  The Orbit Problem is Decidable. 252-261
  
• Joos Heintz, Claus-Peter Schnorr:
  Testing Polynomials which Are Easy to Compute (Extended Abstract). 262-272
  
• Oscar H. Ibarra, Brian S. Leininger:
  The Complexity of the Equivalence Problem for Straight-Line Programs. 273-280
  
• Hartmut Ehrig, Bernd Mahr:
  Complexity of Implementations on the Level of Algebraic Specifications. 281-293
  
• Allan Borodin, Stephen A. Cook:
  A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. 294-301
  
• Richard M. Karp, Richard J. Lipton:
  Some Connections between Nonuniform and Uniform Complexity Classes. 302-309
  
• Jia-Wei Hong:
  On Some Deterministic Space Complexity Problems. 310-317
  
• Chee-Keng Yap:
  Space-time Tradeoffs and First Order Problems in a Model of Programs. 318-325
  
• David A. Carlson, John E. Savage:
  Graph Pebbling with Many Free Pebbles can be Difficult. 326-332
  
• Martin Tompa:
  Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations. 333-338
  
• Joseph JáJá:
  Time-Space Tradeoffs for some Algebraic Problems. 339-350
  
• Nicholas Pippenger:
  Comparative Schematology and Pebbling with Auxiliary Pushdowns (Preliminary Version). 351-356
  
• Wolfgang J. Paul, Joel I. Seiferas, Janos Simon:
  An Information-Theoretic Approach to Time Bounds for On-Line Computation (Preliminary Version). 357-367
  
• Richard M. Karp, Robert Endre Tarjan:
  Linear Expected-Time Algorithms for Connectivity Problems (Extended Abstract). 368-377
  
• Peter A. Bloniarz:
  A Shortest-Path Algorithm with Expected Time O(n^2 log n log ^* n). 378-384
  
• John H. Reif, Paul G. Spirakis:
  Random Matroids. 385-397
  
• Kenneth J. Supowit, David A. Plaisted, Edward M. Reingold:
  Heuristics for Weighted Perfect Matching. 398-419
  
• Greg N. Frederickson, Donald B. Johnson:
  Generalized Selection and Ranking (Preliminary Version). 420-428
  
• F. Frances Yao:
  Efficient Dynamic Programming Using Quadrangle Inequalities. 429-435
  
• Errol L. Lloyd:
  Critical Path Scheduling of Task Systems with Resource and Processor Constraints (Extended Abstract). 436-446
  

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