We show that one-way Π2-alternating Turing machines cannotaccept unary nonregular languages in o(log n) space. This holdsfor an accept mode of space complexity measure, defined asthe worst cost of any accepting computation. This lower boundshould be compared with the corresponding bound for one-wayΣ2-alternating machines, that are able to accept unarynonregular languages in space O(log log n). Thus, Σ2-alternation is more powerful than Π2-alternationfor space bounded one-way machines with unary inputs.
