An optimal lower bound for nonregular languages

Alberto Bertoni, Carlo Mereghetti, and Giovanni Pighizzini

Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
In this paper we prove a tight logn lower bound on the product of space and input head inversions for any Turing machine (equipped with a read only input tape) accepting a nonregular language.