Bibliography - Models of Computation: Exploring the Power of Computing - page 619

[299] T. J. Schaefer, “The Complexity of Satisfiability Problems,” Proc.10thAnn.ACMSymp.Theory
ofComputing(1978), 216-226.
[300] C. P. Schnorr, “Zwei Lineare untere Schranken fur die Komplexitat Boolescher Funktionen,” Com-
puting 13 (1974), 155-171.
[301] C. P. Schnorr, “The Network Complexity and the Turing Machine Complexity of Finite Func-
tions,” ActaInformatica 7 (1976), 95-107.
[302] C. P. Schnorr, “A 3 n -Lower Bound on the Network Complexity of Boolean Functions,” Theoret.
Comp.Sci. 10 (1980), 83-92.
[303] A. Schonhage and V. Strassen, “Schnelle Multiplikation grosser Zahlen,” Computing 7 (1971),
281-292.
[304] U. Schurfeld, “New Lower Bounds on the Formula Size of Boolean Functions,” Acta Informatica
19 (1983), 183-194.
[305] M. P. Schutzenberger, “On Context-Free Languages and Pushdown Automata,” Info.andControl
6 (1963), 246-264.
[306] C. E. Shannon, “A Symbolic Analysis of Relay and Switching Circuits,” Trans. AIEE 57 (1938),
713-723.
[307] C. E. Shannon, “The Synthesis of Two-Terminal Switching Circuits,” Bell Syst. Techn. J. 28
(1949), 59-98.
[308] J. C. Shepherdson and H. E. Sturgis, “Computability of Recursive Functions,” JACM 10 (1963),
217-255.
[309] A. Siegel, “Tight Area Bounds and Provably Good AT 2 Bounds for Sorting Circuits,” New York
University, Report No. 122, New York, 1985.
[310] S. Skyum and L. G. Valiant, “A Complexity Theory Based on Boolean Algebra,” JACM32 (1985),
484-502.
[311] D. D. Sleator and R. E. Tarjan, “Amortized Efficiency of List Update and Paging Rules,” Comm.
ACM 28 (1985), 202-208.
[312] C. H. Smith, ARecursiveIntroductiontotheTheoryofComputation, Springer-Verlag, New York,
1994.
[313] R. Smolensky, “Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complex-
ity,” Proc.19thAnn.ACMSymp.TheoryofComputing(1987), 77-82.
[314] P. M. Spira, “On Time-Hardware Complexity Tradeoffs for Boolean Functions,” Proc.4thHawaii
Int.Symp.SystemScience(1971), 525-527.
[315] M. Spivak, Calculus, W. A. Benjamin, San Francisco, 1976.
[316] L. J. Stockmeyer and A. R. Meyer, “Word Problems Requiring Exponential Time,” Proc.5thAnn.
ACMSymp.TheoryofComputing(1973), 1-9.
[317] L. Stockmeyer and U. Vishkin, “Simulation of Parallel Random Access Machines by Circuits,”
SIAMJ.Comput.13 (1984), 409-422.
[318] H. S. Stone, “Parallel Processing with the Perfect Shuffle,” IEEETrans.Computers C-20 (1971),
153-161.
[319] V. Strassen, “Gaussian Elimination Is Not Optimal,” Numer.Math 13 (1969), 354-356.
[320] B. A. Subbotovskaya, “Realizations of Linear Functions by Formulas Using + , ,” Dokl.Akad.

NaukSSSR(SovietMath.Dokl.) 136 (1961), 553-555, (in Russian); English translation in Soviet
Math. Dokl. 2 (1961), 110-112.

· , −