## 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)

- 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.

9 ×#problem

7 ×#graph

5 ×#algorithm

5 ×#complexity

4 ×#morphism

3 ×#algebra

3 ×#bound

3 ×#implementation

3 ×#on the

3 ×#testing

7 ×#graph

5 ×#algorithm

5 ×#complexity

4 ×#morphism

3 ×#algebra

3 ×#bound

3 ×#implementation

3 ×#on the

3 ×#testing