## Robert L. Constable, Robert W. Ritchie, Jack W. Carlyle, Michael A. Harrison

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

STOC, 1974.

@proceedings{STOC-1974, address = "Seattle, Washington, USA", editor = "Robert L. Constable and Robert W. Ritchie and Jack W. Carlyle and Michael A. Harrison", publisher = "{ACM}", title = "{Proceedings of the Sixth Annual ACM Symposium on Theory of Computing}", year = 1974, }

### Contents (35 items)

- STOC-1974-Chandra #canonical
- Degrees of Translatability and Canonical Forms in Program Schemas: Part I (AKC), pp. 1–12.
- STOC-1974-CourcelleV #axiom #recursion #semantics
- Semantics and Axiomatics of a Simple Recursive Language (BC, JV), pp. 13–26.
- STOC-1974-Valiant #automaton #decidability #equivalence
- The Decidability of Equivalence for Deterministic Finite-Turn Pushdown Automata (LGV), pp. 27–32.
- STOC-1974-CookS #polynomial #requirements
- Storage Requirements for Deterministic Polynomial Time Recognizable Languages (SAC, RS), pp. 33–39.
- STOC-1974-JonesL #polynomial #problem
- Complete Problems for Deterministic Polynomial Time (NDJ, WTL), pp. 40–46.
- STOC-1974-GareyJS #problem
- Some Simplified NP-Complete Problems (MRG, DSJ, LJS), pp. 47–63.
- STOC-1974-HuntR #context-free grammar
- Computational Parallels between the Regular and Context-Free Languages (HBHI, DJR), pp. 64–74.
- STOC-1974-EhrenfeuchtZ #complexity #metric #regular expression
- Complexity Measures for Regular Expressions (AE, HPZ), pp. 75–79.
- STOC-1974-Pratt #matrix #multi #power of
- The Power of Negative Thinking in Multiplying Boolean Matrices (VRP), pp. 80–83.
- STOC-1974-Kirkpatrick #graph #matrix
- Determining Graph Properties from Matrix Representations (DGK), pp. 84–90.
- STOC-1974-Gill #complexity #probability #turing machine
- Computational Complexity of Probabilistic Turing Machines (JTGI), pp. 91–95.
- STOC-1974-Mehlhorn #polynomial #recursion
- Polynomial and Abstract Subrecursive Classes (KM), pp. 96–109.
- STOC-1974-LadnerLS #polynomial
- Comparisons of Polynomial-Time Reducibilities (REL, NAL, ALS), pp. 110–121.
- STOC-1974-PrattRS #power of
- A Characterization of the Power of Vector Machines (VRP, MOR, LJS), pp. 122–134.
- STOC-1974-CookR #calculus #on the #proving
- On the Lengths of Proofs in the Propositional Calculus (SAC, RAR), pp. 135–148.
- STOC-1974-Rackoff #complexity #on the
- On the Complexity of the Theories of Weak Direct Products: A Preliminary Report (CR), pp. 149–160.
- STOC-1974-Robertson #complexity #higher-order #monad
- Structure of Complexity in the Weak Monadic Second-Order Theories of the Natural Numbers (ELR), pp. 161–171.
- STOC-1974-HopcroftW #algorithm #graph #linear #morphism
- Linear Time Algorithm for Isomorphism of Planar Graphs (JEH, JKW), pp. 172–184.
- STOC-1974-Tarjan #graph #testing
- Testing Graph Connectivity (RET), pp. 185–193.
- STOC-1974-Horvath #performance #sorting
- Efficient Stable Sorting with Minimal Extra Space (ECH), pp. 194–215.
- STOC-1974-HyafilPV #algorithm #performance
- An Efficient Algorithm for Computing Optimal Desk Merge Patterns (LH, FP, JV), pp. 216–229.
- STOC-1974-Lipton #branch
- Limitations of Synchronization Primitives with Conditional Branching and Global Variables (RJL), pp. 230–241.
- STOC-1974-Millen #parallel
- Construction with Parallel Derivatives of the Closure of a Parallel Program Schema (JKM), pp. 242–247.
- STOC-1974-VairavanD #parallel #scheduling #source code #strict
- Parallel Scheduling of Programs in a Restricted Model of Computation (KV, RAD), pp. 248–255.
- STOC-1974-Greibach #strict
- Some Restrictions on W-Grammars (SAG), pp. 256–265.
- STOC-1974-Hammer #ll
- A New Grammatical Transformation into LL(k) Form (MH), pp. 266–275.
- STOC-1974-Seiferas #array #multi #nondeterminism
- Observations on Nondeterministic Multidimensional Iterative Arrays (JIS), pp. 276–289.
- STOC-1974-BookNP #bound #context-free grammar #linear #multi
- Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (RVB, MN, MP), pp. 290–296.
- STOC-1974-Rosenberg #array
- Managing Storage for Extendible Arrays (ALR), pp. 297–302.
- STOC-1974-Leeuwen #problem
- A Partial Solution to the Reachability-Problem for Vector-Addition Systems (JvL), pp. 303–309.
- STOC-1974-DobkinL #on the
- On Some Generalizations of Binary Search (DPD, RJL), pp. 310–316.
- STOC-1974-Miller #complexity
- Computational Complexity and Numerical Stability (WM), pp. 317–322.
- STOC-1974-Kung #algorithm #bound #evaluation #parallel
- New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions (HTK), pp. 323–333.
- STOC-1974-Kedem #bound #multi
- Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on the Number of Multiplications (ZMK), pp. 334–341.
- STOC-1974-BorodinC #on the
- On the Number of Additions to Compute Specific Polynomials (AB, SAC), pp. 342–347.

5 ×#complexity

4 ×#multi

4 ×#on the

4 ×#polynomial

3 ×#algorithm

3 ×#bound

3 ×#graph

3 ×#parallel

3 ×#problem

2 ×#array

4 ×#multi

4 ×#on the

4 ×#polynomial

3 ×#algorithm

3 ×#bound

3 ×#graph

3 ×#parallel

3 ×#problem

2 ×#array