Alternating on-line turing machines with only universal states and small space bounds

AbstractLet L[AONTM(L(n))] be the class of sets accepted by L(n) space bounded alternating on-line Turing machines, and L[UONTM(L(n))] be the class of sets accepted by L(n) space bounded alternating on-line Turing machines with only universal states. This note first shows that, for any L(n) such that L(n) ⩾ log log n and limn → ∞[L(n)/log n] = 0, (i) L[UONTM(L(n))] ⊋ L[AONTM(L(n))], (ii) L[UONTM(L(n))] is not closed under complementation, and (iii) L[UONTM(L(n))] is properly contained in the class of sets accepted by L(n) space bounded alternating Turing machines with only universal states. We then show that there exists an infinite hierarchy among L[UONTM(L(n))]'s with log log n ⩽ L(n) ⩽ log n