Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, Richard J. Lipton
Proceedings of the 12th Annual ACM Symposium on Theory of Computing
STOC, 1980.

@proceedings{STOC-1980,
	address       = "Los Angeles, California, USA",
	editor        = "Raymond E. Miller and Seymour Ginsburg and Walter A. Burkhard and Richard J. Lipton",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 12th Annual ACM Symposium on Theory of Computing}",
	year          = 1980,
}

Contents (47 items)

9 ×#problem
7 ×#graph
5 ×#algorithm
5 ×#complexity
4 ×#morphism
3 ×#algebra
3 ×#bound
3 ×#implementation
3 ×#on the
3 ×#testing

STOC-1980-MeyerP #logic

Definability in Dynamic Logic (ARM, RP), pp. 1–7.

STOC-1980-Reif #logic #probability #programming

Logics for Probabilistic Programming (JHR), pp. 8–13.

STOC-1980-Mirkowska #algorithm #axiom #bound #nondeterminism

Complete Axiomatization of Algorithmic Properties of Program Schemes with Bounded Nondeterministic Interpretations (GM), pp. 14–21.

STOC-1980-Pratt #algebra #induction

Dynamic Algebras and the Nature of Induction (VRP), pp. 22–28.

STOC-1980-Ukkonen #automaton #equivalence #realtime

A Decision Method for the Equivalence of some Non-Real-Time Deterministic Pushdown Automata (EU), pp. 29–38.

STOC-1980-Plaisted #independence #on the

On the Distribution of Independent Formulae of Number Theory (DAP), pp. 39–44.

STOC-1980-DeMilloL #consistency #problem

The Consistency of “P = NP” and Related Problems with Fragments of Number Theory (RAD, RJL), pp. 45–57.

STOC-1980-JosephY #independence #question

Independence Results in Computer Science? (DJ, PY), pp. 58–69.

STOC-1980-Lynch #distributed #performance

Fast Allocation of Nearby Resources in a Distributed System (NAL), pp. 70–81.

STOC-1980-Angluin #network

Local and Global Properties in Networks of Processors (DA), pp. 82–93.

STOC-1980-Toueg #network

Deadlock- and Livelock-Free Packet Switching Networks (ST), pp. 94–99.

STOC-1980-Brown #implementation

Kraft Storage and Access for List Implementations (DJB), pp. 100–107.

STOC-1980-Strong #execution #graph

Vector Execution of Flow Graphs (HRS), pp. 108–116.

STOC-1980-SadriU #axiom #database #dependence #relational #scalability

A Complete Axiomatization for a Large Class of Dependencies in Relational Databases (FS, JDU), pp. 117–122.

STOC-1980-Fagin #database #dependence #horn clause

Horn Clauses and Database Dependencies (RF), pp. 123–134.

STOC-1980-OvermarsV #maintenance

Dynamically Maintaining Configurations in the Plane (MHO, JvL), pp. 135–145.

STOC-1980-ChazelleD #detection

Detection is Easier than Computation (BC, DPD), pp. 146–153.

STOC-1980-GuibasY #on the #set

On Translating a Set of Rectangles (LJG, FFY), pp. 154–160.

STOC-1980-Tompa #problem

An Optimal Solution to a Wire-Routing Problem (MT), pp. 161–176.

STOC-1980-FischerP #layout

Optimal Tree Layout (MJF, MP), pp. 177–189.

STOC-1980-BrentK #complexity

The Chip Complexity of Binary Arithmetic (RPB, HTK), pp. 190–200.

STOC-1980-Storer #graph #grid

The Node Cost Measure for Embedding Graphs on the Planar Grid (JAS), pp. 201–210.

STOC-1980-Cypher #approach #problem

An Approach to The k Paths Problem (AC), pp. 211–217.

STOC-1980-Lichtenstein #graph #morphism

Isomorphism for Graphs Embeddable on the Projective Plane (DL), pp. 218–224.

STOC-1980-Miller #bound #graph #morphism #testing

Isomorphism Testing for Graphs of Bounded Genus (GLM), pp. 225–235.

STOC-1980-FilottiM #algorithm #graph #morphism #polynomial

A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus (ISF, JNM), pp. 236–243.

STOC-1980-Hoffmann #graph #morphism #testing

Testing Isomorphism on Cone Graphs (CMH), pp. 244–251.

STOC-1980-KannanL #decidability #problem

The Orbit Problem is Decidable (RK, RJL), pp. 252–261.

STOC-1980-HeintzS #testing

Testing Polynomials which Are Easy to Compute (JH, CPS), pp. 262–272.

STOC-1980-IbarraL #complexity #equivalence #problem #source code

The Complexity of the Equivalence Problem for Straight-Line Programs (OHI, BSL), pp. 273–280.

STOC-1980-EhrigM #algebra #complexity #implementation #specification

Complexity of Implementations on the Level of Algebraic Specifications (HE, BM), pp. 281–293.

STOC-1980-BorodinC #sorting #trade-off

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation (AB, SAC), pp. 294–301.

STOC-1980-KarpL #complexity

Some Connections between Nonuniform and Uniform Complexity Classes (RMK, RJL), pp. 302–309.

STOC-1980-Hong #complexity #on the #problem

On Some Deterministic Space Complexity Problems (JWH), pp. 310–317.

STOC-1980-Yap #first-order #problem #source code #trade-off

Space-time Tradeoffs and First Order Problems in a Model of Programs (CKY), pp. 318–325.

STOC-1980-CarlsonS #graph

Graph Pebbling with Many Free Pebbles can be Difficult (DAC, JES), pp. 326–332.

STOC-1980-Tompa80a #algorithm #implementation #polynomial #sublinear #transitive

Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations (MT), pp. 333–338.

STOC-1980-JaJa #algebra #problem #trade-off

Time-Space Tradeoffs for some Algebraic Problems (JJ), pp. 339–350.

STOC-1980-Pippenger #comparative

Comparative Schematology and Pebbling with Auxiliary Pushdowns (NP), pp. 351–356.

STOC-1980-PaulSS #approach #bound #online

An Information-Theoretic Approach to Time Bounds for On-Line Computation (WJP, JIS, JS), pp. 357–367.

STOC-1980-KarpT #algorithm #linear #problem

Linear Expected-Time Algorithms for Connectivity Problems (RMK, RET), pp. 368–377.

STOC-1980-Bloniarz #algorithm

A Shortest-Path Algorithm with Expected Time O(n^2 log n log ^* n) (PAB), pp. 378–384.

STOC-1980-ReifS #random

Random Matroids (JHR, PGS), pp. 385–397.

STOC-1980-SupowitPR #heuristic

Heuristics for Weighted Perfect Matching (KJS, DAP, EMR), pp. 398–419.

STOC-1980-FredericksonJ #ranking

Generalized Selection and Ranking (GNF, DBJ), pp. 420–428.

STOC-1980-Yao #performance #programming #using

Efficient Dynamic Programming Using Quadrangle Inequalities (FFY), pp. 429–435.

STOC-1980-Lloyd #constraints #scheduling

Critical Path Scheduling of Task Systems with Resource and Processor Constraints (ELL), pp. 436–446.