3-DIMENSIONAL ALTERNATING TURING-MACHINES WITH ONLY UNIVERSAL STATES

We investigate several properties of three-dimensional alternating Tur ning machines whose input tapes are restricted to cubic ones. We first investigate the relationship between the classes of sets accepted by space-bounded and finitely leaf-size bounded five-way three-dimensiona l alternating Turing machines and the classes of sets which are finite intersections of sets accepted by space-bounded five-way three-dimens ional nondeterministic Turing machines. Then, we investigate the accep ting powers of three-dimensional alternating Turing machines with only universal states. (C) Elsevier Science Inc. 1996