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

[233] A. G. Oettinger, “Automatic Syntactic Analysis and the Pushdown Store,” Proc. Symp. Applied
Math. 12 (1961).
[234] Y. Ofman, “On the Algorithmic Complexity of Discrete Functions,” Dokl. Akad. Nauk SSSR
(SovietMath.Dokl.) 145 (1962), 48-51, (in Russian); English translation in Soviet Math. Dokl. 7
(7) (1963), 589-591.
[235] C. H. Papadimitriou, ComputationalComplexity, Addison-Wesley, Reading, MA, 1994.
[236] C. H. Papadimitriou and M. Sipser, “Communication Complexity,” J.Comp.SystemSciences 28
(1984), 260-269.
[237] M. S. Paterson, “An Introduction to Boolean Function Complexity,” Asterique38-39 (1976), 183-
201.
[238] M. S. Paterson, “Complexity of Monotone Networks for Boolean Matrix Product,” Theoret.
Comp.Sci. 1 (1979), 13-20.
[239] M. S. Paterson and C. E. Hewitt, “Comparative Schematology,” in Proc. Project MAC Conf.
ConcurrentSystemsandParallelComputation, Woods Hole, MA, 1970, 119-127.
[240] M. S. Paterson and L. G. Valiant, “Circuit Size Is Nonlinear in Depth,” Theoret. Comp. Sci. 2
(1976), 397-400.
[241] M. S. Paterson, “New Bounds on Formula Size,” in Proc. 3rdGIConf. Theoret.Computer Sci-
ence, Springer-Verlag, Lecture Notes in Computer Science, 48 , Berlin, Heidelberg, and New York,
1977, 17-26.
[242] M. S. Paterson, N. Pippenger, and U. Zwick, “Faster Circuits and Shorter Formulae for Multi-
ple Addition, Multiplication and Symmetric Boolean Functions,” Proc. 31st Ann. IEEE Symp.
FoundationsofComputerScience(1990), 642-650.
[243] M. S. Paterson, N. Pippenger, and U. Zwick, “Optimal Carry-Save Networks,” in BooleanFunc-
tionComplexity, M. S. Paterson, ed., Cambridge University Press, London Mathematical Society
Lecture Note Series, 169, Cambridge, 1992, 174-201.
[244] W. Paul, “A 2 . 5 N Lower Bound for the Combinational Complexity of Boolean Functions,” SIAM
J.Comput. 6 (1977), 427-443.
[245] W. J. Paul and R. E. Tarjan, “Time-Space Trade-Offs in a Pebble Game,” Acta Informatica 10
(1978), 111-115.
[246] W. J. Paul, R. E. Tarjan, and J. R. Celoni, “Space Bounds for a Game on Graphs,” Math. Systems
Theory 10 (1977), 239-251.
[247] G. L. Peterson, “An Upper Bound on the Size of Formulae for Symmetric Boolean Functions,”
Dept. Computer Science, Univ. Washington, Tech. Report 78-03-01, 1978.
[248] N. Pippenger, “Short Formulae for Symmetric Functions,” IBM T. J. Watson Research Center,
Research Report RC-5143, Yorktown Heights, NY, 1974.
[249] N. Pippenger, “On Simultaneous Resource Bounds,” JACM 26 (1979), 361-381.
[250] N. Pippenger, “On Another Boolean Matrix,” Theoret.Comp.Scii. 11 (1980), 49-56.
[251] N. Pippenger, “Pebbling,” Proc. 5thAnn. IBMSymp.Math. Foundations of Computer Science
(1980).
[252] N. Pippenger and M. J. Fischer, “Relations Among Complexity Measures,” JACM 26 (1979),
361-381.
[253] N. Pippenger and L. G. Valiant, “Shifting Graphs and Their Properties,” JACM 23 (1976), 423-
432.
[254] N. Pippenger, “A Time-Space Trade-off,” JACM 25 (1978), 509-512.