A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines
Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154
Košice, Slovakia; (email@example.com)
2 Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154 Košice, Slovakia; (firstname.lastname@example.org)
Accepted: 28 November 2000
We show that one-way Π2-alternating Turing machines cannot accept unary nonregular languages in o(log n) space. This holds for an accept mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ2-alternating machines, that are able to accept unary nonregular languages in space O(log log n). Thus, Σ2-alternation is more powerful than Π2-alternation for space bounded one-way machines with unary inputs.
Mathematics Subject Classification: 68Q17 / 68Q45
Key words: Alternation / lower bounds / nonregular languages / space complexity / Turing machine.
© EDP Sciences, 2000