Alternating on-line Turing machines with only universal states and small space bounds (Q1083207)

Let \({\mathcal L}[AONTM(L(n))]\) be the class of sets accepted by L(n) space bounded alternating on-line Turing machines, and \({\mathcal 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)\(\geq \log \log n\) and \(\lim_{n\to \infty}[L(n)/\log n]=0\), (i) \({\mathcal L}[UONTM(L(n))]\subseteq {\mathcal L}[AONTM(L(n))]\), (ii) \({\mathcal L}[UONTM(L(n))]\) is not closed under complementation, and (iii) \({\mathcal 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 \({\mathcal L}[UONTM(L(n))]'s\) with log log \(n\leq L(n)\leq \log n\).