Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard, Alfred V. Aho
Proceedings of the 11th Annual ACM Symposium on Theory of Computing
STOC, 1979.

@proceedings{STOC-1979,
	address       = "Atlanta, Georgia, USA",
	editor        = "Michael J. Fischer and Richard A. DeMillo and Nancy A. Lynch and Walter A. Burkhard and Alfred V. Aho",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 11th Annual ACM Symposium on Theory of Computing}",
	year          = 1979,
}

Contents (37 items)

8 ×#complexity
6 ×#on the
6 ×#problem
3 ×#bound
3 ×#data type
3 ×#database
3 ×#graph
3 ×#parallel
3 ×#polynomial
3 ×#relational

STOC-1979-ValdesTL #graph #parallel #recognition

The recognition of Series Parallel digraphs (JV, RET, ELL), pp. 1–12.

STOC-1979-GalilN #network

Network Flow and Generalized Path Compression (ZG, AN), pp. 13–26.

STOC-1979-FilottiMR #graph #on the

On Determining the Genus of a Graph in O(v^O(g)) Steps (ISF, GLM, JHR), pp. 27–37.

STOC-1979-ChazelleD

Decomposing a Polygon into its Convex Parts (BC, DPD), pp. 38–48.

STOC-1979-FlajoletFV #sequence

Computing Integrated Costs of Sequences of Operations with Application to Dictionaries (PF, JF, JV), pp. 49–61.

STOC-1979-Fredman #data type #problem #query

A Near Optimal Data Structure for a Type of Range Query Problem (MLF), pp. 62–66.

STOC-1979-Kosaraju #multi #on the #problem

On a Multidimensional Search Problem (SRK), pp. 67–73.

STOC-1979-SedgewickS #complexity

The Complexity of Finding Periods (RS, TGS), pp. 74–80.

STOC-1979-Thompson #complexity

Area-Time Complexity for VLSI (CDT), pp. 81–88.

STOC-1979-TouegU #concurrent #network

Deadlock-Free Packet Switching Networks (ST, JDU), pp. 89–98.

STOC-1979-RosenbergWG #data type

Storage Representations for Tree-Like Data Structures (ALR, DW, ZG), pp. 99–107.

STOC-1979-MunroS #data type

Implicit Data Structures (JIM, HS), pp. 108–117.

STOC-1979-Shamir #complexity #on the

On the Cryptocomplexity of Knapsack Systems (AS), pp. 118–129.

STOC-1979-Angluin #set #string

Finding Patterns Common to a Set of Strings (DA), pp. 130–141.

STOC-1979-GurariI #complexity #equivalence #linear #problem #set #source code

The Complexity of the Equivalence Problem for Counter Machines, Semilinear Sets, and Simple Programs (EMG, OHI), pp. 142–152.

STOC-1979-DeMilloL #complexity #logic

Some Connections between Mathematical Logic and Complexity Theory (RAD, RJL), pp. 153–159.

STOC-1979-Berman #axiom #semantics

A Completeness Technique for D-Axiomatizable Semantics (FB), pp. 160–166.

STOC-1979-MeyerW #logic #on the #power of

On the Expressive Power of Dynamic Logic (ARM, KW), pp. 167–175.

STOC-1979-ODonnell #independence #programming language #theorem

A Programming Language Theorem Which Is Independent of Peano Arithmetic (MO), pp. 176–188.

STOC-1979-Valiant

Negation Can Be Exponentially Powerful (LGV), pp. 189–196.

STOC-1979-JaJa #commutative #complexity #on the

On the Complexity of Bilinear Forms with Commutativity (JJ), pp. 197–208.

STOC-1979-Yao #complexity

Some Complexity Questions Related to Distributive Computing (ACCY), pp. 209–213.

STOC-1979-Ladner #communication #complexity #csp #problem #process

The Complexity of Problems in Systems of Communicating Sequential Processes (REL), pp. 214–223.

STOC-1979-Peterson #modelling #parallel #trade-off

Time-Space Trade-Offs for Asynchronous Parallel Models: Reducibilities and Equivalences (GLP), pp. 224–230.

STOC-1979-Kosaraju79a #algorithm #array #graph #parallel #performance #problem

Fast Parallel Processing Array Algorithms for some Graph Problems (SRK), pp. 231–236.

STOC-1979-GilbertLT #polynomial #problem

The Pebbling Problem is Complete in Polynomial Space (JRG, TL, RET), pp. 237–248.

STOC-1979-Valiant79a #algebra

Completeness Classes in Algebra (LGV), pp. 249–261.

STOC-1979-LengauerT #bound #trade-off

Upper and Lower Bounds on Time-Space Tradeoffs (TL, RET), pp. 262–277.

STOC-1979-Long #on the #polynomial

On γ-Reducibility versus Polynomial Time Many-One Reducibility (TJL), pp. 278–287.

STOC-1979-Reif #game studies

Universal Games of Incomplete Information (JHR), pp. 288–308.

STOC-1979-ChandraH #database #query #relational

Computable Queries for Relational Data Bases (AKC, DH), pp. 309–318.

STOC-1979-BeeriMSU #database #equivalence #relational

Equivalence of Relational Database Schemes (CB, AOM, YS, JDU), pp. 319–329.

STOC-1979-Maier #database #relational

Minimum Covers in the Relational Database Model (DM), pp. 330–337.

STOC-1979-Cook #polynomial

Deterministic CFL’s Are Accepted Simultaneously in Polynomial Time and Log Squared Space (SAC), pp. 338–345.

STOC-1979-Kosaraju79aa #realtime #simulation

Real-Time Simulation of Concatenable Double-Ended Queues by Double-Ended Queues (SRK), pp. 346–351.

STOC-1979-Ruzzo #bound

Tree-Size Bounded Alternation (WLR), pp. 352–359.

STOC-1979-Sipser #automaton #bound

Lower Bounds on the Size of Sweeping Automata (MS), pp. 360–364.