Regular sets are accepted by deterministic or nondeterministic finite-state automata, which are deterministic or nondeterministic Turing machines (DTMs and NTMs) using constant space. It is known that even if the NTM is allowed o ( loglog n ) space, its power does not increase beyond regular languages. If alternations are also allowed, then the corresponding result holds for online alternating Turing machines (ATMs), but for offline ATMs the only known lower bound for accepting nonregular sets was o ( logloglog n ). In this paper, the author improves this bound to o ( loglog n ) for offline ATMs.

This result is interesting and is not obvious because other complexity measures exist under which the lower bound for NTMs is larger than that for ATMs. Also, offline loglog n space-bounded ATMs are more powerful than online loglog n space-bounded ATMs, which are more powerful than the same space-bounded NTMs (the author proves this result in the appendix). Further, different definitions of space-bounded ATMs exist under which the loglog n alternating-space-bounded classes provably differ.

The proof of the main theorem uses crossing sequences and a cut-and-paste argument, and is technical and nontrivial. It is well written and clearly explained (all the required references are clearly cited in the appropriate places); nonetheless, the details may not be of interest, except to the researcher in the field. The statement of the theorem itself is of more general interest, however.