| Issue |
RAIRO-Theor. Inf. Appl.
Volume 34, Number 5, September/October 2000
|
|
|---|---|---|
| Page(s) | 357 - 372 | |
| DOI | https://doi.org/10.1051/ita:2000101 | |
| Published online | 15 April 2002 | |
A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines
1
Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154
Košice, Slovakia; (geffert@kosice.upjs.sk)
2
Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154
Košice, Slovakia; (popely@kosice.upjs.sk)
Received:
30
June
2000
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.