Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines

Authors

Allan Borodin, University of Toronto
Stephen Cook, University of Toronto
Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1983

Abstract

It is shown that a probabilistic Turing acceptor or transducer running within space bound Scan be simulated by a time S² parallel machine and therefore by a space S² deterministic machine. (Previous simulations ran in space S⁶.) In order to achieve these simulations, known algorithms are extended for the computation of determinants in small arithmetic parallel time to computations having small Boolean parallel time, and this development is applied to computing the completion of stochastic matrices. The method introduces a generalization of the ring of integers, called well-endowed rings. Such rings possess a very efficient parallel implementation of the basic (+,−,×) ring operations.

Rights Information

© 1983 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1016/S0019-9958(83)80060-6

Recommended Citation

A. B. Borodin, S. A. Cook, N. Pippenger, "Parallel Computation for Well-Endowed Rings and Space Bounded Probabilistic Machines", (with ), Info. and Contr., 58 (1983), 113-136, doi: 10.1016/S0019-9958(83)80060-6