  We study a generalized version of reversal bounded Turing machines where,
apart from several tapes on which the number of head reversals is bounded by
r(n), there are several further tapes on which head reversals remain
unrestricted, but size is bounded by s(n). Recently, such machines were
introduced as a formalization of a computation model that restricts random
access to external memory and internal memory space. Here, each of the tapes
with a restriction on the head reversals corresponds to an external memory
device, and the tapes of restricted size model internal memory. We use
ST(r(n),s(n),O(1)) to denote the class of all problems that can be solved by
deterministic Turing machines that comply to the above resource bounds.
Similarly, NST and RST, respectively, are used for the corresponding
nondeterministic and randomized classes.
  While previous papers focused on lower bounds for particular problems,
including sorting, the set equality problem, and several query evaluation
problems, the present paper addresses the relations between the (R,N)ST-classes
and classical complexity classes and investigates the structural complexity of
the (R,N)ST-classes. Our main results are (1) a trade-off between internal
memory space and external memory head reversals, (2) correspondences between
the (R,N)ST-classes and ``classical'' time-bounded, space-bounded,
reversal-bounded, and circuit complexity classes, and (3) hierarchies of
(R)ST-classes in terms of increasing numbers of head reversals on external
memory tapes.
