13. STOC 1981: Milwaukee, Wisconsin, USA

• Karel Culik II, Tero Harju:
  The omega-Sequence Equivalence Problem for DOL Systems Is Decidable. 1-6
  
• Paul Chew:
  Unique Normal Forms in Term Rewriting Systems with Repeated Variables. 7-18
  
• Frank M. Hawrusik, K. N. Venkataraman, Ann Yasuhara:
  Classes of Functions for Computing on Binary Trees (Extended Abstract). 19-27
  
• Balakrishnan Krishnamurthy, Robert N. Moll:
  Examples of Hard Tautologies in the Propositional Calculus. 28-37
  
• Daniel Leivant:
  The Complexity of Parameter Passing in Polymorphic Procedures (or: Programming Language Theorems Independent of Very Strong Theories). 38-45
  
• David E. Muller, Paul E. Schupp:
  Pushdown Automata, Graphs, Ends, Second-Order Logic, and Reachability Problems. 46-54
  
• Deborah Joseph, Paul Young:
  Fast Programs for Initial Segments and Polynomial Time Computation in Weak Models of Arithmetic (Preliminary Abstract). 55-61
  
• S. Rao Kosaraju:
  Localized Search in Sorted Lists. 62-69
  
• Bernard Chazelle:
  Convex Decompositions of Polyhedra. 70-79
  
• Chul E. Kim, Azriel Rosenfeld:
  Digital Straightness and Convexity (Extended Abstract). 80-89
  
• Gaston H. Gonnet, J. Ian Munro:
  A Linear Probing Sort and its Analysis (Preliminary Draft). 90-95
  
• Faith E. Fich:
  Lower Bounds for the Cycle Detection Problem. 96-105
  
• Zvi Galil, Joel I. Seiferas:
  Time-Space-Optimal String Matching. 106-113
  
• Daniel Dominic Sleator, Robert Endre Tarjan:
  A Data Structure for Dynamic Trees. 114-122
  
• Andrew Chi-Chih Yao:
  On the Parallel Computation for the Knapsack Problem. 123-127
  
• Eshrat Arjomandi, Michael J. Fischer, Nancy A. Lynch:
  A Difference in Efficiency between Synchronous and Asynchronous Systems. 128-132
  
• John H. Reif, Paul G. Spirakis:
  Distributed Algorithms for Synchronizing Interprocess Communication within Real Time. 133-145
  
• Tat-hung Chan:
  Reversal Complexity of Counter Machines. 146-157
  
• Janos Simon:
  Space-Bounded Probabilistic Turing Machine Complexity Classes Are Closed under Complement (Preliminary Version). 158-167
  
• Alberto Bertoni, Giancarlo Mauri, Nicoletta Sabadini:
  A Characterization of the Class of Functions Computable in Polynomial Time on Random Access Machines. 168-176
  
• Pavol Duris, Zvi Galil:
  Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version). 177-188
  
• K. N. King:
  Measures of Parallelism in Alternating Computation Trees (Extended Abstract). 189-201
  
• Esko Ukkonen, Eljas Soisalon-Soininen:
  LALR(k) Testing is PSPACE-Complete. 202-206
  
• Burkhard Monien, Ivan Hal Sudborough:
  Bandwidth Constrained NP-Complete Problems. 207-217
  
• James B. Orlin:
  The Complexity of Dynamic Languages and Dynamic Optimization Problems. 218-227
  
• Akeo Adachi, Shigeki Iwata, Takumi Kasai:
  Low Level Complexity for Combinatorial Games. 228-237
  
• Ernst W. Mayr:
  An Algorithm for the General Petri Net Reachability Problem. 238-246
  
• Zvi Galil, Wolfgang J. Paul:
  An Efficient General Purpose Parallel Computer. 247-262
  
• Leslie G. Valiant, Gordon J. Brebner:
  Universal Schemes for Parallel Communication. 263-277
  
• Daniel J. Kleitman, Frank Thomson Leighton, Margaret Lepley, Gary L. Miller:
  New Layouts for the Shuffle-Exchange Graph (Extended Abstract). 278-292
  
• Mike Paterson, Walter L. Ruzzo, Lawrence Snyder:
  Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract). 293-299
  
• Richard J. Lipton, Robert Sedgewick:
  Lower Bounds for VLSI. 300-307
  
• Andrew Chi-Chih Yao:
  The Entropic Limitations on VLSI Computations (Extended Abstract). 308-311
  
• Danny Dolev, Kevin Karplus, Alan Siegel, Alex Strong, Jeffrey D. Ullman:
  Optimal Wiring between Rectangles. 312-317
  
• Bernard Chazelle, Louis Monier:
  A Model of Computation for VLSI with Related Complexity Results. 318-325
  
• Jia-Wei Hong, H. T. Kung:
  I/O Complexity: The Red-Blue Pebble Game. 326-333
  
• Jia-Wei Hong, Arnold L. Rosenberg:
  Graphs that Are Almost Binary Trees (Preliminary Version). 334-341
  
• Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky:
  Embedded Implicational Dependencies and their Inference Problem. 342-354
  
• Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis:
  Properties of Acyclic Database Schemes. 355-362
  
• Mihalis Yannakakis:
  Issues of Correctness in Database Concurrency Control by Locking. 363-367
  
• Francesco Parisi-Presicce:
  On the Faithful Regular Extensions of Iterative Algebras. 368-374
  
• Robert S. Streett:
  Propositional Dynamic Logic of Looping and Converse. 375-383
  
• Ashok K. Chandra, Joseph Y. Halpern, Albert R. Meyer, Rohit Parikh:
  Equations between Regular Terms and an Application to Process Logic. 384-390
  

Last update Sat May 18 19:50:28 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page