13. STOC 1981: Milwaukee, Wisconsin, USA
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

- 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