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

[255] E. L. Post, “Finite Combinatory Processes,” J.SymbolicLogic 1 (1936), 103-105.
[256] V. R. Pratt, “The Power of Negative Thinking in Multiplying Boolean Matrices,” SIAMJ.Comput.
4 (1974), 326-330.
[257] V. R. Pratt, “Every Prime Has a Succinct Certificate,” SIAMJ.Comput.4 (1975), 214-220.
[258] F. P. Preparata, “A Mesh-Connected Area-Time Optimal VLSI Multiplier of Large Integers,” IEEE
Trans.Computers C-32 (1983), 194-198.
[259] F. P. Preparata and D. E. Muller, “Efficient Parallel Evaluation of Boolean Expressions,” IEEE
Trans.Computers C-25 (1976), 548-549.
[260] F. P. Preparata and J. E. Vuillemin, “Area-Time Optimal VLSI Networks for Multiplying Matrices,”
InfoProcessingLetters 11 (1980), 77-80.
[261] F. P. Preparata and J. E. Vuillemin, “Optimal Integrated-Circuit Implementation of Triangular
Matrix Inversion,” ParallelProcessing(1980), 211-216.
[262] F. P. Preparata and J. E. Vuillemin, “The Cube-Connected Cycles: A Versatile Network for Parallel
Computation,” Comm.ACM 24 (1981), 300-309.
[263] F. P. Preparata, “Optimal Three-Dimensional VLSI Layouts,” Math. Systems Theory 16 (1983),
1-8.
[264] P. Pudlak, “Bounds for Hodes-Specker Theorem,” in LogicandMachines:DecisionProblemsand
Complexity, Springer-Verlag, Lecture Notes in Computer Science, 171 , Berlin, Heidelberg, and
New York, 1984, 421-445.
[265] M. J. Quinn, ParallelComputing:TheoryandPractice, McGraw-Hill, New York, 1994.
[266] M. O. Rabin and D. Scott, “Finite Automata and Their Decision Problems,” IBMJ.Res.Devel.
3 (1959), 114-125.
[267] A. Ranade, “How to Emulate Shared Memory,” Proc. 28th Ann. IEEE Symp. Foundations of
ComputerScience(1987), 185-194.
[268] B. Randell, ed., TheOriginsofDigitalComputers:SelectedPapers, Springer-Verlag, Berlin, Hei-
delberg, and New York, 1982.
[269] R. Raz and A. Wigderson, “Monotone Circuits for Matching Require Linear Depth,” Proc.22nd
Ann.ACMSymp.TheoryofComputing(1990), 287-292.
[270] A. A. Razborov, “Lower Bounds on the Monotone Complexity of Some Boolean Functions,” Dokl.
Akad.NaukSSSR(SovietMath.Dokl.) 281 (1985), 798-801, (in Russian); English translation in
Soviet Math. Dokl. 31 (1985), 354-357.
[271] A. A. Razborov, “A Lower Bound on the Monotone Network Complexity of the Logical Perma-
nent,” Mat.Zametki 37 (1985), 887-900, (in Russian); English translation in Math. Notes 37 (6)
(1985), 485-493.
[272] A. A. Razborov, “Lower Bounds on the Size of Bounded Depth Networks over a Complete Basis
with Logical Addition,” Mat. Zametki 41 (1987), 598-607, (in Russian); English translation in
Math. Notes 41 (4) (1987), 333-338.
[273] A. A. Razborov, “On the Method of Approximations,” Proc. 21st Ann. ACMSymp. Theory of
Computing(1989), 167-176.
[274] N. P. Red'kin, “Proof of Minimality of Circuits Consisting of Functional Elements,” Probl.Kibern.
23 (1973), 83-102, (in Russian); English translation in: Syst. Theory Research 23 (1973) 102-107.
[275] N. P. Red'kin, “On the Realization of Monotone Boolean Functions by Contact Circuits,” Probl.
Kibern. 35 (1979), 87-110.
[276] N. P. Red'kin, “Minimal Realization of a Binary Adder,” Probl.Kibern. 38 (1981), 181-216, 272.