Proceedings of the 13th Annual ACM Symposium on Theory of Computing
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
EDIT!
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter


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

TCS
DBLP
Scholar
Full names Links ISxN
@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)

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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.