A remark on middle space bounded alternating Turing machines

Carlo Mereghetti and Giovanni Pighizzini

Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
We prove a tight log n lower bound on middle space for one--way alternating Turing machines that accept nonregular tally languages. This is to be compared with the optimal loglogn lower bound in the literature for nonregular languages over arbitrary alphabets.