Proceedings of the 13th Annual ACM Symposium on Theory of Computing
STOC, 1981.

@proceedings{STOC-1981,
	address       = "Milwaukee, Wisconsin, USA",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 13th Annual ACM Symposium on Theory of Computing}",
	year          = 1981,
}

Contents (43 items)

8 ×#problem
7 ×#complexity
4 ×#bound
4 ×#parallel
3 ×#graph
3 ×#logic
3 ×#performance
2 ×#algorithm
2 ×#automaton
2 ×#communication

STOC-1981-CulikH #decidability #equivalence #problem

The ω-Sequence Equivalence Problem for DOL Systems Is Decidable (KCI, TH), pp. 1–6.

STOC-1981-Chew #normalisation #term rewriting

Unique Normal Forms in Term Rewriting Systems with Repeated Variables (PC), pp. 7–18.

STOC-1981-HawrusikVY

Classes of Functions for Computing on Binary Trees (FMH, KNV, AY), pp. 19–27.

STOC-1981-KrishnamurthyM #calculus

Examples of Hard Tautologies in the Propositional Calculus (BK, RNM), pp. 28–37.

STOC-1981-Leivant #complexity #independence #parametricity #polymorphism #programming language #theorem

The Complexity of Parameter Passing in Polymorphic Procedures (or: Programming Language Theorems Independent of Very Strong Theories) (DL), pp. 38–45.

STOC-1981-MullerS #automaton #graph #higher-order #logic #problem #reachability

Pushdown Automata, Graphs, Ends, Second-Order Logic, and Reachability Problems (DEM, PES), pp. 46–54.

STOC-1981-JosephY #modelling #performance #polynomial #source code

Fast Programs for Initial Segments and Polynomial Time Computation in Weak Models of Arithmetic (DJ, PY), pp. 55–61.

STOC-1981-Kosaraju #locality

Localized Search in Sorted Lists (SRK), pp. 62–69.

STOC-1981-Chazelle

Convex Decompositions of Polyhedra (BC), pp. 70–79.

STOC-1981-KimR

Digital Straightness and Convexity (CEK, AR), pp. 80–89.

STOC-1981-GonnetM #analysis #linear

A Linear Probing Sort and its Analysis (GHG, JIM), pp. 90–95.

STOC-1981-Fich #bound #detection #problem

Lower Bounds for the Cycle Detection Problem (FEF), pp. 96–105.

STOC-1981-GalilS #string

Time-Space-Optimal String Matching (ZG, JIS), pp. 106–113.

STOC-1981-SleatorT #data type

A Data Structure for Dynamic Trees (DDS, RET), pp. 114–122.

STOC-1981-Yao #on the #parallel #problem

On the Parallel Computation for the Knapsack Problem (ACCY), pp. 123–127.

STOC-1981-ArjomandiFL #difference #performance

A Difference in Efficiency between Synchronous and Asynchronous Systems (EA, MJF, NAL), pp. 128–132.

STOC-1981-ReifS #algorithm #communication #distributed #realtime

Distributed Algorithms for Synchronizing Interprocess Communication within Real Time (JHR, PGS), pp. 133–145.

STOC-1981-Chan #complexity

Reversal Complexity of Counter Machines (ThC), pp. 146–157.

STOC-1981-Simon #bound #complexity #probability #turing machine

Space-Bounded Probabilistic Turing Machine Complexity Classes Are Closed under Complement (JS), pp. 158–167.

STOC-1981-BertoniMS #polynomial #random

A Characterization of the Class of Functions Computable in Polynomial Time on Random Access Machines (AB, GM, NS), pp. 168–176.

STOC-1981-DurisG #automaton

Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (PD, ZG), pp. 177–188.

STOC-1981-King #metric #parallel

Measures of Parallelism in Alternating Computation Trees (KNK), pp. 189–201.

STOC-1981-UkkonenS #lalr #testing

LALR(k) Testing is PSPACE-Complete (EU, ESS), pp. 202–206.

STOC-1981-MonienS #problem

Bandwidth Constrained NP-Complete Problems (BM, IHS), pp. 207–217.

STOC-1981-Orlin #complexity #optimisation #problem

The Complexity of Dynamic Languages and Dynamic Optimization Problems (JBO), pp. 218–227.

STOC-1981-AdachiIK #combinator #complexity #game studies #low level

Low Level Complexity for Combinatorial Games (AA, SI, TK), pp. 228–237.

STOC-1981-Mayr #algorithm #petri net #problem #reachability

An Algorithm for the General Petri Net Reachability Problem (EWM), pp. 238–246.

STOC-1981-GalilP #parallel #performance

An Efficient General Purpose Parallel Computer (ZG, WJP), pp. 247–262.

STOC-1981-ValiantB #communication #parallel

Universal Schemes for Parallel Communication (LGV, GJB), pp. 263–277.

STOC-1981-KleitmanLLM #graph

New Layouts for the Shuffle-Exchange Graph (DJK, FTL, ML, GLM), pp. 278–292.

STOC-1981-PatersonRS #bound

Bounds on Minimax Edge Length for Complete Binary Trees (MP, WLR, LS), pp. 293–299.

STOC-1981-LiptonS #bound

Lower Bounds for VLSI (RJL, RS), pp. 300–307.

STOC-1981-Yao81a

The Entropic Limitations on VLSI Computations (ACCY), pp. 308–311.

STOC-1981-DolevKSSU

Optimal Wiring between Rectangles (DD, KK, AS, AS, JDU), pp. 312–317.

STOC-1981-ChazelleM #complexity

A Model of Computation for VLSI with Related Complexity Results (BC, LM), pp. 318–325.

STOC-1981-HongK #complexity #game studies

I/O Complexity: The Red-Blue Pebble Game (JWH, HTK), pp. 326–333.

STOC-1981-HongR #graph

Graphs that Are Almost Binary Trees (JWH, ALR), pp. 334–341.

STOC-1981-ChandraLM #dependence #embedded #problem

Embedded Implicational Dependencies and their Inference Problem (AKC, HRL, JAM), pp. 342–354.

STOC-1981-BeeriFMMUY #database

Properties of Acyclic Database Schemes (CB, RF, DM, AOM, JDU, MY), pp. 355–362.

STOC-1981-Yannakakis #concurrent #correctness #database

Issues of Correctness in Database Concurrency Control by Locking (MY), pp. 363–367.

STOC-1981-Parisi-Presicce #algebra #on the

On the Faithful Regular Extensions of Iterative Algebras (FPP), pp. 368–374.

STOC-1981-Streett #logic

Propositional Dynamic Logic of Looping and Converse (RSS), pp. 375–383.

STOC-1981-ChandraHMP #equation #logic #process

Equations between Regular Terms and an Application to Process Logic (AKC, JYH, ARM, RP), pp. 384–390.