## Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, Alfred V. Aho

*Proceedings of the 10th Annual ACM Symposium on Theory of Computing*

STOC, 1978.

@proceedings{STOC-1978, address = "San Diego, California, USA", editor = "Richard J. Lipton and Walter A. Burkhard and Walter J. Savitch and Emily P. Friedman and Alfred V. Aho", publisher = "{ACM}", title = "{Proceedings of the 10th Annual ACM Symposium on Theory of Computing}", year = 1978, }

### Contents (38 items)

- STOC-1978-Megiddo #combinator #optimisation
- Combinatorial Optimization with Rational Objective Functions (NM), pp. 1–12.
- STOC-1978-Lueker #graph #problem
- Maximization Problems on Graphs with Edge Weights Chosen from a Normal Distribution (GSL), pp. 13–18.
- STOC-1978-BrownT #linear #representation
- A Representation for Linear Lists with Movable Fingers (MRB, RET), pp. 19–29.
- STOC-1978-StorerS #metaprogramming
- The Macro Model for Data Compression (JAS, TGS), pp. 30–39.
- STOC-1978-LapaughR #morphism #problem
- The Subgraph Homeomorphism Problem (ASL, RLR), pp. 40–50.
- STOC-1978-Miller #morphism #on the
- On the n^log n Isomorphism Technique: A Preliminary Report (GLM), pp. 51–58.
- STOC-1978-CarterFGMW #approximate
- Exact and Approximate Membership Testers (LC, RWF, JG, GM, MNW), pp. 59–65.
- STOC-1978-EngelfrietRS #transducer
- Tree Transducers, L Systems and Two-Way Machines (JE, GR, GS), pp. 66–74.
- STOC-1978-RaoultV #equivalence #recursion #semantics #source code
- Operational and Semantic Equivalence between Recursive Programs (JCR, JV), pp. 75–85.
- STOC-1978-Katseff #problem
- A New Solution to the Critical Section Problem (HPK), pp. 86–88.
- STOC-1978-Goldschlager #approach #modelling #parallel
- A Unified Approach to Models of Synchronous Parallel Machines (LMG), pp. 89–94.
- STOC-1978-ScioreT
- Computability Theory in Admissible Domains (ES, AT), pp. 95–104.
- STOC-1978-MillerY #on the #parallel
- On Formulating Simultaneity for Studying Parallelism and Synchronization (REM, CKY), pp. 105–113.
- STOC-1978-FortuneW #parallel #random
- Parallelism in Random Access Machines (SF, JW), pp. 114–118.
- STOC-1978-ThatcherWW #data type #power of #specification
- Data Type Specification: Parameterization and the Power of Specification Techniques (JWT, EGW, JBW), pp. 119–132.
- STOC-1978-Filotti #algorithm #graph #performance #polynomial
- An Efficient Algorithm for Determining Whether a Cubic Graph is Toroidal (ISF), pp. 133–142.
- STOC-1978-Wegener #complexity #polynomial
- Switching Functions Whose Monotone Complexity Is Nearly Quadratic (IW), pp. 143–149.
- STOC-1978-Lynch #complexity #metric #parametricity
- Straight-Line Program Length as a Parameter for Complexity Measures (NAL), pp. 150–161.
- STOC-1978-Pan #complexity
- Computational Complexity of Computing Polynomials over the Fields of Real and Complex Numbers (VYP), pp. 162–172.
- STOC-1978-JaJa #evaluation
- Optimal Evaluation of Pairs of Bilinear Forms (JJ), pp. 173–183.
- STOC-1978-GabowK #algorithm #graph
- Algorithms for Edge Coloring Bipartite Graphs (HNG, OK), pp. 184–192.
- STOC-1978-Hyafil #evaluation #on the #parallel
- On the Parallel Evaluation of Multivariate Polynomials (LH), pp. 193–195.
- STOC-1978-Tompa #trade-off #using
- Time-Space Tradeoffs for Computing Functions, Using Connectivity Properties of their Circuits (MT), pp. 196–204.
- STOC-1978-GurariI #problem
- An NP-Complete Number-Theoretic Problem (EMG, OHI), pp. 205–215.
- STOC-1978-Schaefer #complexity #problem #satisfiability
- The Complexity of Satisfiability Problems (TJS), pp. 216–226.
- STOC-1978-RivestMKWS #fault
- Coping with Errors in Binary Search Procedures (RLR, ARM, DJK, KW, JS), pp. 227–232.
- STOC-1978-BrussM #formal method #on the
- On Time-Space Classes and Their Relation to the Theory of Real Addition (ARB, ARM), pp. 233–239.
- STOC-1978-KirkpatrickH #on the #problem
- On the Completeness of a Generalized Matching Problem (DGK, PH), pp. 240–245.
- STOC-1978-Dowd #proving #representation
- Propositional Representation of Arithmetic Proofs (MD), pp. 246–252.
- STOC-1978-Yannakakis #problem
- Node- and Edge-Deletion NP-Complete Problems (MY), pp. 253–264.
- STOC-1978-Lewis #complexity #on the #problem
- On the Complexity of the Maximum Subgraph Problem (JML), pp. 265–274.
- STOC-1978-SakodaS #automaton #finite #nondeterminism
- Nondeterminism and the Size of Two Way Finite Automata (WJS, MS), pp. 275–286.
- STOC-1978-Kozen #recursion
- Indexing of Subrecursive Classes (DK), pp. 287–295.
- STOC-1978-Baudet #algorithm #analysis
- An Analysis of the Full αβ Pruning Algorithm (GMB), pp. 296–313.
- STOC-1978-CaseS #induction
- Anomaly Hierarchies of Mechanized Inductive Inference (JC, CS), pp. 314–319.
- STOC-1978-ReddyL #bound #quantifier
- Presburger Arithmetic with Bounded Quantifier Alternation (CRR, DWL), pp. 320–325.
- STOC-1978-Pratt #logic
- A Practical Decision Method for Propositional Dynamic Logic: Preliminary Report (VRP), pp. 326–337.
- STOC-1978-Rackoff #algorithm #probability
- Relativized Questions Involving Probabilistic Algorithms (CR), pp. 338–342.

8 ×#problem

6 ×#on the

5 ×#complexity

4 ×#algorithm

4 ×#parallel

3 ×#graph

2 ×#evaluation

2 ×#morphism

2 ×#polynomial

2 ×#recursion

6 ×#on the

5 ×#complexity

4 ×#algorithm

4 ×#parallel

3 ×#graph

2 ×#evaluation

2 ×#morphism

2 ×#polynomial

2 ×#recursion