## Ashok K. Chandra, Detlef Wotschke, Emily P. Friedman, Michael A. Harrison

*Proceedings of the Eighth Annual ACM Symposium on Theory of Computing*

STOC, 1976.

@proceedings{STOC-1976, address = "Hershey, Pennsylvania, USA", editor = "Ashok K. Chandra and Detlef Wotschke and Emily P. Friedman and Michael A. Harrison", publisher = "{ACM}", title = "{Proceedings of the Eighth Annual ACM Symposium on Theory of Computing}", year = 1976, }

### Contents (30 items)

- STOC-1976-PapadimitriouS #complexity #problem
- Some Complexity Results for the Traveling Salesman Problem (CHP, KS), pp. 1–9.
- STOC-1976-GareyGJ #geometry #problem
- Some NP-Complete Geometric Problems (MRG, RLG, DSJ), pp. 10–22.
- STOC-1976-MandersA #polynomial #problem
- NP-Complete Decision Problems for Quadratic Polynomials (KLM, LMA), pp. 23–29.
- STOC-1976-HartmanisB #morphism #on the #set
- On Isomorphisms and Density of NP and Other Complete Sets (JH, LB), pp. 30–40.
- STOC-1976-Schaefer #complexity #finite #game studies #problem
- Complexity of Decision Problems Based on Finite Two-Person Perfect-Information Games (TJS), pp. 41–49.
- STOC-1976-CardozaLM #commutative #exponential #petri net #problem
- Exponential Space Complete Problems for Petri Nets and Commutative Semigroups: Preliminary Report (EC, RJL, ARM), pp. 50–54.
- STOC-1976-Hirschberg #algorithm #component #parallel #problem #transitive
- Parallel Algorithms for the Transitive Closure and the Connected Component Problems (DSH), pp. 55–57.
- STOC-1976-ThompsonK #parallel #sorting
- Sorting on a Mesh-Connected Parallel Computer (CDT, HTK), pp. 58–64.
- STOC-1976-Doeppner #abstraction #on the #parallel #source code
- On Abstractions of Parallel Programs (TWDJ), pp. 65–72.
- STOC-1976-Owicki #consistency #deduction #parallel #source code #verification
- A Consistent and Complete Deductive System for the Verification of Parallel Programs (SSO), pp. 73–86.
- STOC-1976-Wand #hoare
- A New Incompleteness Result for Hoare’s System (MW), pp. 87–91.
- STOC-1976-Kimura #algebra #communication #process
- An Algebraic System for Process Structuring and Interprocess Communication (TK), pp. 92–100.
- STOC-1976-Kosaraju #on the
- On Structuring Flowcharts (SRK), pp. 101–111.
- STOC-1976-GrahamHR #context-free grammar #on the #polynomial #recognition
- On Line Context Free Language Recognition in Less than Cubic Time (SLG, MAH, WLR), pp. 112–120.
- STOC-1976-FongU #graph
- Finding the Depth of a Flow Graph (ACF, JDU), pp. 121–125.
- STOC-1976-HuntS #problem #reachability
- Dichotomization, Reachability, and the Forbidden Subgraph Problem (HBHI, TGS), pp. 126–134.
- STOC-1976-IbarraK #problem
- A Useful Device for Showing the Solvability of Some Decision Problems (OHI, CEK), pp. 135–140.
- STOC-1976-Sudborough #automaton #context-free grammar #multi #on the #power of
- On Deterministic Context-Free Languages, Multihead Automata, and the Power of an Auxiliary Pushdown Store (IHS), pp. 141–148.
- STOC-1976-PaulTC #bound #game studies #graph
- Space Bounds for a Game of Graphs (WJP, RET, JRC), pp. 149–160.
- STOC-1976-Galil #algorithm #realtime #recognition #string
- Real-Time Algorithms for String-Matching and Palindrome Recognition (ZG), pp. 161–173.
- STOC-1976-LiptonS #evaluation
- Evaluation of Polynomials with Super-Preconditioning (RJL, LJS), pp. 174–180.
- STOC-1976-PatersonW #linear #unification
- Linear Unification (MP, MNW), pp. 181–186.
- STOC-1976-GuibasS #analysis
- The Analysis of Double Hashing (LJG, ES), pp. 187–191.
- STOC-1976-Yao #algorithm #behaviour #on the #set
- On the Average Behavior of Set Merging Algorithms (ACCY), pp. 192–195.
- STOC-1976-Valiant
- Universal Circuits (LGV), pp. 196–203.
- STOC-1976-Pippenger
- The Realization of Monotone Boolean Functions (NP), pp. 204–210.
- STOC-1976-Burkhard #retrieval
- Associative Retrieval Trie Hash-Coding (WAB), pp. 211–219.
- STOC-1976-BentleyS #divide and conquer #multi
- Divide-and-Conquer in Multidimensional Space (JLB, MIS), pp. 220–230.
- STOC-1976-LeeP
- Location of a Point in a Planar Subdivision and its Applications (DTL, FPP), pp. 231–235.
- STOC-1976-MachteyY
- Simple Gödel Numberings, Translations, and the P-Hierarchy (MM, PY), pp. 236–243.

8 ×#problem

6 ×#on the

4 ×#parallel

3 ×#algorithm

2 ×#complexity

2 ×#context-free grammar

2 ×#game studies

2 ×#graph

2 ×#multi

2 ×#polynomial

6 ×#on the

4 ×#parallel

3 ×#algorithm

2 ×#complexity

2 ×#context-free grammar

2 ×#game studies

2 ×#graph

2 ×#multi

2 ×#polynomial