## William C. Rounds, Nancy Martin, Jack W. Carlyle, Michael A. Harrison

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

STOC, 1975.

@proceedings{STOC-1975, address = "Albuquerque, New Mexico, USA", editor = "William C. Rounds and Nancy Martin and Jack W. Carlyle and Michael A. Harrison", publisher = "{ACM}", title = "{Proceedings of the Seventh Annual ACM Symposium on Theory of Computing}", year = 1975, }

### Contents (31 items)

- STOC-1975-LiptonD #complexity #evaluation #integer #metric
- Complexity Measures and Hierarchies for the Evaluation of Integers, Polynomials, and n-linear Forms (RJL, DPD), pp. 1–5.
- STOC-1975-RivestV #proving
- A Generalization and Proof of the Aanderaa-Rosenberg Conjecture (RLR, JV), pp. 6–11.
- STOC-1975-HyafilK #complexity #evaluation #linear #parallel
- The Complexity of Parallel Evaluation of Linear Recurrence (LH, HTK), pp. 12–22.
- STOC-1975-Yao #on the #polynomial
- On Computing the Minima of Quadratic Forms (ACCY), pp. 23–26.
- STOC-1975-Paul #bound #combinator #complexity
- A 2.5 n-lower Bound on the Combinatorial Complexity of Boolean Functions (WJP), pp. 27–36.
- STOC-1975-FischerMP #bound
- Lower Bounds on the Size of Boolean Formulas: Preliminary Report (MJF, ARM, MP), pp. 37–44.
- STOC-1975-Valiant #bound #complexity #on the
- On Non-linear Lower Bounds in Computational Complexity (LGV), pp. 45–53.
- STOC-1975-HuntS #complexity #on the #problem
- On the Complexity of Grammar and Related Problems (HBHI, TGS), pp. 54–65.
- STOC-1975-EvenT #combinator #polynomial #problem
- a Combinatorial Problem which is Complete in Polynomial Space (SE, RET), pp. 66–71.
- STOC-1975-Galil #bound #complexity #on the
- On the Validity and Complexity of Bounded Resolution (ZG), pp. 72–82.
- STOC-1975-Cook #calculus #proving
- Feasibly Constructive Proofs and the Propositional Calculus (SAC), pp. 83–97.
- STOC-1975-EgliC #concept #programming language #semantics
- Computability Concepts for Programming Language Semantics (HE, RLC), pp. 98–106.
- STOC-1975-OppenC #data type #proving #source code
- Proving Assertions about Programs that Manipulate Data Structures (DCO, SAC), pp. 107–116.
- STOC-1975-EhrenfeuchtR #formal method #on the #predict
- On (Un)predictability of Formal Languages (AE, GR), pp. 117–120.
- STOC-1975-Skyum #on the #parallel
- On Decomposing Languages Defined by Parallel Devices (SS), pp. 121–125.
- STOC-1975-Perrault #theorem #transducer
- Intercalation Theorems for Tree Transducer Languages (CRP), pp. 126–136.
- STOC-1975-EhrenfeuchtR75a #combinator #interactive #on the
- On the (Combinatorial) Structure of L Languages without Interactions (AE, GR), pp. 137–144.
- STOC-1975-Wotschke #polynomial #problem #recognition
- Degree-Languages, Polynomial Time Recognition, and the LBA Problem (DW), pp. 145–152.
- STOC-1975-GinsburgL #comparative #complexity
- Comparative Complexity of Grammar Forms (SG, NAL), pp. 153–158.
- STOC-1975-RosenbergS #array
- Hashing Schemes for Extendible Arrays (Extended Arrays) (ALR, LJS), pp. 159–166.
- STOC-1975-Pratt #analysis #modelling #optimisation
- Four Models for the Analysis of Optimization of Program Control Structures (TWP), pp. 167–176.
- STOC-1975-AhoU #graph
- Node Listings for Reducible Flow Graphs (AVA, JDU), pp. 177–185.
- STOC-1975-LiptonED #complexity #data type
- The Complexity of Control Structures and Data Structures (RJL, SCE, RAD), pp. 186–193.
- STOC-1975-MannaS #recursion #source code
- The Optimal Fixedpoint of Recursive Programs (ZM, AS), pp. 194–206.
- STOC-1975-AhoJ #code generation
- Optimal Code Generation for Expression Trees (AVA, SCJ), pp. 207–217.
- STOC-1975-Wagner #complexity #on the #problem #string
- On the Complexity of the Extended String-to-String Correction Problem (RAW), pp. 218–223.
- STOC-1975-Shamos #complexity #geometry
- Geometric Complexity (MIS), pp. 224–233.
- STOC-1975-Miller #testing
- Riemann’s Hypothesis and Tests for Primality (GLM), pp. 234–239.
- STOC-1975-Fredman #probability #sorting
- Two Applications of a Probabilistic Search Technique: Sorting x + y and Building Balanced Search Trees (MLF), pp. 240–244.
- STOC-1975-RoseT #algorithm #aspect-oriented
- Algorithmic Aspects of Vertex Elimination (DJR, RET), pp. 245–254.
- STOC-1975-BoothL #algorithm #graph #linear
- Linear Algorithms to Recognize Interval Graphs and Test for the Consecutive Ones Property (KSB, GSL), pp. 255–265.

10 ×#complexity

8 ×#on the

4 ×#bound

4 ×#problem

3 ×#combinator

3 ×#polynomial

3 ×#proving

2 ×#algorithm

2 ×#data type

2 ×#evaluation

8 ×#on the

4 ×#bound

4 ×#problem

3 ×#combinator

3 ×#polynomial

3 ×#proving

2 ×#algorithm

2 ×#data type

2 ×#evaluation