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

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

8 ×#complexity

6 ×#on the

6 ×#problem

3 ×#bound

3 ×#data type

3 ×#database

3 ×#graph

3 ×#parallel

3 ×#polynomial

3 ×#relational

6 ×#on the

6 ×#problem

3 ×#bound

3 ×#data type

3 ×#database

3 ×#graph

3 ×#parallel

3 ×#polynomial

3 ×#relational