## John E. Hopcroft, Emily P. Friedman, Michael A. Harrison

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

STOC, 1977.

@proceedings{STOC-1977, address = "Boulder, Colorado, USA", editor = "John E. Hopcroft and Emily P. Friedman and Michael A. Harrison", publisher = "{ACM}", title = "{Proceedings of the Ninth Annual ACM Symposium on Theory of Computing}", year = 1977, }

### Contents (31 items)

- STOC-1977-Itai #graph
- Finding a Minimum Circuit in a Graph (AI), pp. 1–10.
- STOC-1977-YaoAR #bound #problem
- An Ω(n² log n) Lower Bound to the Shortest Paths Problem (ACCY, DA, RLR), pp. 11–17.
- STOC-1977-Tarjan #maintenance #set
- Reference Machines Require Non-linear Time to Maintain Disjoint Sets (RET), pp. 18–29.
- STOC-1977-AngluinV #algorithm #performance #probability
- Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings (DA, LGV), pp. 30–41.
- STOC-1977-Brown #complexity #maintenance #queue
- The Complexity of Priority Queue Maintenance (MRB), pp. 42–48.
- STOC-1977-GuibasMPR #linear #representation
- A New Representation for Linear Lists (LJG, EMM, MFP, JRR), pp. 49–60.
- STOC-1977-SacerdoteT #decidability #problem #reachability
- The Decidability of the Reachability Problem for Vector Addition Systems (GSS, RLT), pp. 61–76.
- STOC-1977-ChandraM #database #implementation #query #relational
- Optimal Implementation of Conjunctive Queries in Relational Data Bases (AKC, PMM), pp. 77–90.
- STOC-1977-PetersonF #distributed #problem
- Economical Solutions for the Critical Section Problem in a Distributed System (GLP, MJF), pp. 91–97.
- STOC-1977-Rosenthal #programming
- Nonserial Dynamic Programming Is Optimal (AR), pp. 98–105.
- STOC-1977-CarterW
- Universal Classes of Hash Functions (LC, MNW), pp. 106–112.
- STOC-1977-GonnetM #analysis
- The Analysis of an Improved Hashing Technique (GHG, JIM), pp. 113–121.
- STOC-1977-Beatty #ll #theorem
- Iteration Theorems for LL(k) Languages (JCB), pp. 122–131.
- STOC-1977-PrabhalaS #comparison #set #stack
- A Comparison of Instruction Sets for Stack Machines (BP, RS), pp. 132–142.
- STOC-1977-Miller #graph #morphism
- Graph Isomorphism, General Remarks (GLM), pp. 143–150.
- STOC-1977-AdlemanM
- Reducibility, Randomness, and Intractability (LMA, KLM), pp. 151–163.
- STOC-1977-Kozen #algebra #complexity
- Complexity of Finitely Presented Algebras (DK), pp. 164–177.
- STOC-1977-KintalaF #nondeterminism #strict
- Computations with a Restricted Number of Nondeterministic Steps (CMRK, PCF), pp. 178–185.
- STOC-1977-SimonG #polynomial
- Polynomial Reducibilities and Upward Diagonalizations (IS, JG), pp. 186–194.
- STOC-1977-Simon #on the
- On Feasible Numbers (JS), pp. 195–207.
- STOC-1977-Sudborough #automaton #bound
- Separating Tape Bounded Auxiliary Pushdown Automata Classes (IHS), pp. 208–217.
- STOC-1977-Paul #on the
- On Time Hierarchies (WJP), pp. 218–222.
- STOC-1977-Hartmanis #complexity #proving
- Relations Between Diagonalization, Proof Systems, and Complexity Gaps (JH), pp. 223–227.
- STOC-1977-LynchB #performance #programming
- Efficient Reducibility Between Programming Systems: Preliminary Report (NAL, EKB), pp. 228–238.
- STOC-1977-LeongS #multi #realtime #simulation
- New Real-Time Simulations of Multihead Tape Units (BLL, JIS), pp. 239–248.
- STOC-1977-HarelPS #axiom #deduction #proving #recursion #source code
- A Complete Axiomatic System for Proving Deductions about Recursive Programs (DH, AP, JS), pp. 249–260.
- STOC-1977-HarelMP #logic #source code
- Computability and Completeness in Logics of Programs (DH, ARM, VRP), pp. 261–268.
- STOC-1977-Constable #formal method #logic #on the #programming
- On the Theory of Programming Logics (RLC), pp. 269–285.
- STOC-1977-FischerL #logic #source code
- Propositional Modal Logic of Programs (MJF, REL), pp. 286–294.
- STOC-1977-ODonnell #combinator #equation #lisp #logic #program transformation #recursion
- Subtree Replacement Systems: A Unifying Theory for Recursive Equations, LISP, Lucid and Combinatory Logic (MO), pp. 295–305.
- STOC-1977-HennessyA #nondeterminism
- Parameter-Passing Mechanisms and Nondeterminism (MH, EAA), pp. 306–311.

4 ×#logic

3 ×#complexity

3 ×#on the

3 ×#problem

3 ×#programming

3 ×#source code

2 ×#bound

2 ×#graph

2 ×#maintenance

2 ×#nondeterminism

3 ×#complexity

3 ×#on the

3 ×#problem

3 ×#programming

3 ×#source code

2 ×#bound

2 ×#graph

2 ×#maintenance

2 ×#nondeterminism