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
Abstract
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.