In this paper we introduce a formal model for random access computers and argue that the
model is a good one to use in the theory of computational complexity. Results are proved …

A model of computation based on random access machines operating in parallel and
sharing a common memory is presented. The computational power of this model is related to …

We consider random access machines with a multiplication operation, having the added
capability of computing logical operations on register are considered both as an integer and …

2.2 Machine models Throughout this thesis we will be considering computing devices as
acceptors of sets of sequences, or languages. Al ternatively we may view these as 0-1 …

This paper studies two aspects of the power of space-bounded probabilistic Turing
machines. Section 2 presents a simple alternative proof of Simon's recent result [13] that …

The RAM model of Cook and Reckhow~ s extended to allow parallel recursive calls and the
elementary theory of such machines is developed The uniform cost criterion is used The …

We study the power of deterministic successor RAM's with extra instructions like+,*,⋎ and
the associated classes of problems decidable in polynomial time. Our main results are NP …

A new class of machine models as a framework for the rational discussion of programming
languages is introduced. In particular, a basis is provided for endowing programming …

It is well known that every set in P has small circuits [13]. Adleman [1] has recently proved
the stronger result that every set accepted in polynomial time by a randomized Turing …

A relationship is established between (i) parallel random-access machines that allow many
processors to concurrently read from or write into a common memory including simultaneous …