13. STOC 1981
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, May 11-13, 1981, Milwaukee, Wisconsin, USA. ACM 1981
- 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
- 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
Copyright © Fri Mar 12 17:22:12 2010
by Michael Ley (ley@uni-trier.de)
